PKU 1293 Duty Free Shop

PKU

http://poj.org/problem?id=1293

２種類のチョコレートがそれぞれm個,l個ある。
そして、n個の箱があり、それぞれチョコレートをC_i個入れなければいけない。

異なる種類のチョコレートを同じ箱に入れることなく、全ての箱をチョコレートで満たすことが出来るかどうかを判定し、出来る場合はm個あるほうのチョコレートをどの箱に入れるかを答えろというような問題。

dp[i番目の箱までみて、i番目の箱をチョコmを入れるのに使ったか][i番目の箱][チョコmをj個使った]
みたいなDPをして、経路復元みたいなことをしました。

int m,l;
int box[2000];
bool dp[2][2000][1001];

void solve(){
  int n;
  cin>>n;
  int sum=0;
  rep(i,n){
    cin>>box[i];
    sum+=box[i];
  }

  if(sum<=l){
    cout<<0<<endl;
    return;
  }
  memset(dp,0,sizeof(dp));  

  if(box[0]<=m) dp[0][0][box[0]] = true;
  dp[1][0][0]=true;
  
  for(int i=1;i<n;++i)
    for(int j=0;j<=m;++j){
      dp[1][i][j] |= dp[0][i-1][j]|dp[1][i-1][j];
      if(j>=box[i])
        dp[0][i][j] |= dp[0][i-1][j-box[i]]|dp[1][i-1][j-box[i]];
      if(sum-j>l || !dp[0][i][j]) continue;
      vector<int> use;

      bool flag=0;
      int tm=j;
      int tu=i;

      while(tu>=0){
        if(!flag){
          use.pb(tu);
          tm -= box[tu];
        }
        if(tm==0) break;
        if(tu==0) break;
        --tu;
        if(dp[0][tu][tm]) flag=0;
        else flag=true;
      }
      
      cout<<SZ(use);
      reverse(ALL(use));
      FOR(it,use) cout<<' '<<*it+1;
      cout<<endl;
      return;
    }
  
  cout<<"Impossible to distribute"<<endl;

}

main(){
  while(cin>>m>>l,m|l)
    solve();
}