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; }