PKU 3628 Bookshelf 2
http://poj.org/problem?id=3628
n(<=20)匹の牛がいて、それぞれ高さh_iである。
何匹か積み上げて高さs>=bにしたい。
この時、s-bの最小値を求めよというような問題。
TLEなりにくいようです。
全探索っぽく書いて普通に通りました。
int in[20]; int insum[21]; int n,b; ll ans=100000000LL; void dfs(int ne,ll sum){ if(sum+insum[n]-insum[ne]<b)return; if(sum>=b){ ans=min(ans,sum-b); return; } for(int i=ne;i<n;i++) dfs(i+1,sum+in[i]); } main(){ cin>>n>>b; rep(i,n){ cin>>in[i]; insum[i+1]=insum[i]+in[i]; } dfs(0,0); cout<<ans<<endl; }
(追記)何を勘違いしたのO(N!)だと考えていたようです。