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