POJ-3046 : Ant Counting
問題概要
T(<1000)色のボールが全体でA個ある。色iの玉はnum[i](<100)個ある。サイズsの部分集合の個数をw[s]とするとsum_{S<=s<=B} w[s]を求める問題。
解法
新たにはさんで行くタイプのDP。ways[i][s] = {color [0,i)までで作れるサイズsの集合の個数}とするとways[i+1][s] = sum_{max(0,s-num[i])<=k<=s} ways[i][k]なので、部分和を累積和で加速する。
acceptされたコード
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX_N = (int)(1e5); const int MAX_T = 1000; const int MOD = (int)(1e6); int T, A, S, B; int as[MAX_T]; int ways[MAX_N + 1], accum[MAX_N + 2]; void init() { scanf("%d%d%d%d", &T, &A, &S, &B); memset(as, 0, sizeof(as)); for (int _ = 0; _ < A; ++_) { int a; scanf("%d", &a); ++as[a-1]; } } int solve() { memset(ways, 0, sizeof(ways)); ways[0] = 1; for (int col = 0; col < T; ++col) { for (int i = 0; i <= A; ++i) { accum[i+1] = (accum[i] + ways[i]) % MOD; } for (int num = 0; num <= A; ++num) { ways[num] = (accum[num + 1] - accum[max(0, num - as[col])] + MOD) % MOD; } } int ans = 0; for (int i = S; i <= B; ++i) { ans = (ans + ways[i]) % MOD; } return ans; } int main() { init(); printf("%d\n", solve()); return 0; }