AOJ 2333 - My friends are small

問題文 : ぼくの友達は小さい

解法 :
友達を重さでソートし, "使わない友達"を決めると, いくつまでの重量の組み合わせをいれるかを決めることが出来る.
この組み合わせを求める部分は, 典型的なナップサック問題を解くDPで求めることが出来る.
よって、O(NW)時間でこの問題を解くことが可能である.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>

#define MOD (1000000007)

using namespace std;

int N, W;
int w[256];
int dp[202][10001];

int main()
{
	scanf("%d %d", &N, &W);
	
	for (int i = 0; i < N; i++){
		scanf("%d", &w[i]);
	}
	sort(w, w + N);
	reverse(w, w + N);
	
	dp[0][0] = 1;
	for (int i = 0; i < N; i++){
		memcpy(dp[i + 1], dp[i], sizeof(dp[i]));
		for (int j = W - w[i]; j >= 0; j--){
			dp[i + 1][j + w[i]] += dp[i][j];
			dp[i + 1][j + w[i]] %= MOD;
		}
	}
	reverse(w, w + N);
	int all, res;
	all = res = 0;
	for (int i = 0; i < N; i++){
		for (int j = max(0, W - all - w[i] + 1); j <= W - all - (i ? w[i - 1] : 0); j++){
				res = (res + dp[N - i][j]) % MOD;
		}
		all += w[i];
	}
	
	printf("%d\n", res);
	
	return (0);
}