2333 - My friends are small

AOJ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2333

問題

略

解法

入力（a[i]とする）を降順でソートする。
a[i]までの合計をsum[i]とする。
答えを、
(a[n-1]まで全て使うときの解) + (a[n-2]まで全て使い、a[n-1]は使わないときの解) + ... + (a[0]まで全て使い、a[1]は使わないときの解) + (何も使わない時の解)
として求める。
a[i]まで全て使うときの解は、sum[i]入れた上でa[i+1]が入らないようなa[i+2]以降の入れ方の総数である。
これは、a[i+2]以降を使って重さjを作る場合の数をdp[j]として持っておけば、O(W)で求めることが出来る。
このDPはただのナップサック問題である。

ソース

ll MOD = 1e9+7;
ll dp[10001];
int main() {
  int n, w;
  cin >> n >> w;
  int a[n];
  int sum = 0;
  REP(i, n) {
    cin >> a[i];
    sum += a[i];
  }
  sort(a, a+n, greater<int>());
  dp[0] = 1;
  ll ans = 0;
  if (sum <= w) ans = 1;
  REP(i, n) {
    sum -= a[i];
    for (int j=max(0,w-sum-a[i]+1); j<=w-sum; ++j) {
      ans = (ans + dp[j]) % MOD;
    }
    for (int j=w-a[i]; j>=0; --j) {
      dp[j+a[i]] = (dp[j+a[i]] + dp[j]) % MOD;
    }
  }
  cout << ans << endl;
}