TopCoder SRM 316 Div1 Medium PlacingPieces

問題

n個の幅の等しい長方形があり、それぞれの長さはpieces[i]である。
この長方形を、幅の等しい、長さがLの長方形の中に入れる。

中の長方形は重なったり、外にはみでていたりしてはならない。
中の長方形を、「他の使っていない長方形をどこにも追加することができない」ように並べる。
中にいれる長方形の数の最小値を求めよ。

制約条件

n≦30
pieces[i]≦100
L≦1000

方針

総当たり+ナップサック。

長さがpieces[s]未満の長方形を全て使うとき、
長方形と長方形の間隔は0〜pieces[s]未満にできる。
dp[i]を、長さiの地点まで長方形を並べるときの、長方形の数の最小値とする、
ナップサック問題のような動的計画法により、
このときの最小値が求まる。

ただし、整数でない座標に長方形を置くこともできるので、少し工夫が必要。
全部の間隔がpieces[s]ぴったりだとダメで、pieces[s]-EPSならよい。
dp[i][j]を、j=1ならpieces[s]より小さい間隔があったときのiの個数の最小値、
j=0ならpieces[s]より小さい間隔がまだないときのiの個数の最小値とする。

ソースコード

vi len;
int l,n,dp[1001][2];
int solve(int s){
  rep(i,l+1)rep(j,2)dp[i][j]=inf;
  int sum=0, cnt=0;
  rep(i,n)if(len[i]<len[s])sum+=len[i], cnt++;
  if(sum>l)return inf;
  for(int i=sum;i<=l&&i<=sum+cnt*len[s];i++)
    dp[i][i<sum+cnt*len[s]]=cnt;
  
  rep(i,n)if(len[i]>=len[s]){
    for(int j=l;j>=0;j--)rep(k,2)if(dp[j][k]!=inf){
      if(j+len[i]>l)continue;
      rep(sp,len[s]+1){
        int nj=j+sp+len[i], nk=k||sp<len[s];
        nj=min(nj,l);
        dp[nj][nk]=min(dp[nj][nk],dp[j][k]+1);
      }
    }
  }
  int res=inf;
  for(int i=max(0,l-len[s]);i<=l;i++){
    res=min(res,dp[i][1]);
    if(i>l-len[s])res=min(res,dp[i][0]);
  }
  return res;
}
class PlacingPieces {
  public:
  int optimalPlacement(int L, vector <int> pieces) {
    len=pieces;
    n=len.size();
    l=L;
    int ans=n;
    rep(s,n)ans=min(ans,solve(s));
    
    return ans;
  }
};