POJ 3400 Dropping the stones

問題

2つのどぶにN個の石を投げる。
それぞれの石には重さp[i]および価値v[i]が定まっており、
次の条件を満たすように好きな順にどぶに投げ入れる。

  • 最初に投げるのはAのどぶへ
  • 二つのどぶに入っている石の重さの差がDを超えたら投げ入れるどぶを換える


このとき、Bのどぶには最大でどれだけの価値の石が入れられるか求めよ。

制約条件

N≦10
その他の値≦10000

方針

Nが小さいので再帰で全探索して間に合いそう。
実際にやってみるとギリギリで間に合う。(1500msくらい)

ソースコード

int N,D,p[10],v[10];
int cost[2],weight[2],ans;
bool use[10];

void dfs(int c,int cur){
  if(c==N){
    ans=max(ans,cost[1]);
    return;
  }
  rep(i,N)if(!use[i]){
    use[i]=1;
    weight[cur]+=p[i];
    cost[cur]+=v[i];
    dfs(c+1,weight[cur]>weight[1-cur]+D?1-cur:cur);
    
    weight[cur]-=p[i];
    cost[cur]-=v[i];
    use[i]=0;
  }
}
int main(){
  scanf("%d%d",&N,&D);
  rep(i,N)scanf("%d%d",p+i,v+i);
  dfs(0,0);
  printf("%d\n",ans);
  return 0;
}