题目链接

Ant Counting POJ - 3046

思路

$$ dp[i][j] 表示 从前i种物品中选出j个的方案数。\\\\可得dp[i][j] = \sum_{k = 0}^{min \left(j, t[i] \right)}dp[i - 1][j - k]\\\\很明显dp[i][j] 与 dp[i][j - 1] 的重复部分有很多\\\\进而可以优化成dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1 - t[i]]\\\\注意边界条件dp[i][0]初始化成1,因为从前i种中选0个的方案数就是1。 $$

时间复杂度

$$ O(TB) $$

代码

#include <cstdio>

using namespace std;

const int MAXN = 1e5 + 10;
const int MOD = 1e6;

int t[MAXN];
int dp[2][MAXN];

int add(int x, int y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
    return x;
}

int sub(int x, int y) {
    x -= y;
    if (x < 0) {
        x += MOD;
    }
    return x;
}

int main() {
    int T, A, S, B;
    scanf("%d%d%d%d", &T, &A, &S, &B);// don't forget &
    while (A--) {
        int x;
        scanf("%d", &x);// don't forget &
        t[x]++;
    }
    dp[0][0] = dp[1][0] = 1;
    for (int i = 1; i <= T; i++) {
        for (int j = 1; j <= B; j++) {
            if (j - 1 - t[i] >= 0) {
                dp[i & 1][j] = add(dp[i & 1][j - 1], sub(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j - 1 - t[i]]));
            } else {
                dp[i & 1][j] = add(dp[i & 1][j - 1], dp[(i - 1) & 1][j]);
            }
        }
    }
    int ans = 0;
    for (int i = S; i <= B; i++) {
        ans = add(ans, dp[T & 1][i]);
    }
    printf("%d", ans);
    return 0;
}