ここから最大得点の160pt問題。
とはいえFは妙に簡単…。
http://qupc2014.contest.atcoder.jp/tasks/qupc2014_f
問題
N個の設備があり、それを移動するコストはD[i]である。
N個中M個以上の設備を、合計コストT以下で移動する組み合わせを答えよ。
解法
N<=100、M<=100、T<=10000なので、設備数と合計コストでDPするだけ。
メモリがO(MT)、時間がO(NMT)で済むので余裕。
int N,T,M; ll mo=1000000009; int D[1001]; ll dp[2][101][10001]; void solve() { int f,i,j,k,l,x,y; cin>>N>>T>>M; dp[0][0][0]=1; FOR(i,N) { int cur=i%2,tar=cur^1; cin>>D[i]; memmove(dp[tar],dp[cur],sizeof(dp[cur])); for(x=N-1;x>=0;x--) for(y=T;y>=0;y--) { if(y+D[i]>T) continue; dp[tar][x+1][y+D[i]]=(dp[tar][x+1][y+D[i]]+dp[cur][x][y])%mo; } } ll ret=0; for(x=M;x<=N;x++) FOR(y,T+1) ret+=dp[N%2][x][y]; cout << ret%mo << endl; }
まとめ
配点の割にえらく簡単な問題。