AOJ 2333 My friends are small
まず、wを昇順でソートする。
dp[i][j] = #{w[i]以降のみを使って和がjとなる組}
sum[i] = w[i]までの和
とするとき、次の3つの場合を考えれば良い。
(i) w[0]を使わない
(ii) w[0]からw[i]までを使い、w[i+1]を使わない(0 <= i < N-1)
(iii) 全て使う
(i)の場合, (i=1,j) s.t. 0 <= W - j < w[0] について、dp[i][j]をresに加える
(ii)の場合、 (i,j) s.t. 0 <= W - sum[i] - j < w[i+1] について、dp[i][j]をresに加える
(iii)の場合、 W >= sum[N-1] ならばresに1を加える。
#include <bits/stdc++.h> #define FOR(i,a,b) for(int i=(a);i<(int)(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(x) (x).begin(),(x).end() using namespace std; const int INF = 1e9; const int MOD = 1000000007; int main() { int N,W; cin >> N >> W; vector<int> w(N),sum(N); REP(i,N) cin >> w[i]; sort(ALL(w)); sum[0] = w[0]; REP(i,N-1) sum[i+1] = sum[i] + w[i+1]; vector<vector<int>> dp(N+1, vector<int> (W+1,0)); dp[N][0] = 1; for(int i=N-1;i>=0;i--)REP(j,W+1){ if(j >= w[i]) dp[i][j] += dp[i+1][j-w[i]]; dp[i][j] += dp[i+1][j]; dp[i][j] %= MOD; } int res = 0; if(W >= sum[N-1]) res++; REP(j,W+1) if(j > W - w[0]){ res = (res + dp[1][j]) % MOD; } REP(i,N-1)REP(j,W+1){ if(j > W - sum[i+1] && j <= W - sum[i]){ res = (res + dp[i+2][j]) % MOD; } } cout << res << endl; return 0; }