QUPC2014 : F - 設備移転

ここから最大得点の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;
	
}

まとめ

配点の割にえらく簡単な問題。