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