POJ 3046 Ant Counting 簡單DP

題意也比較簡單了。  大概是： 給出T種數字。每種各有N[i]個 然後用這些數字構成一些序列， 問x長度到y長度的序列有多少種   那麼就是DP了 dp[i][j] 表示前i種數字構成長度為j的序列有多少種 然後 dp[i][j] = sigma(dp[i - 1][j - k]) k的范圍是0~N[i] 注意到這裡的sigma(dp[i - 1][j - k]) 可以用部分和算一下   然後因為總共的數字個數可能有10W個 有1000種數組。 所以需要開滾動數組來搞 復雜度的話 是 O(sigma(num[i] * (T + 1 - i))) 最壞是1億

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define MAXN 111111
#define INF 1000000007
using namespace std;
int dp[2][MAXN], num[1111];
int sum[MAXN], up[1111];
int main()
{
    int T, S, A, B, x;
    scanf("%d%d%d%d", &T, &A, &S, &B);
    for(int i = 1; i <= A; i++)
    {
        scanf("%d", &x);
        num[x]++;
    }
    for(int i = 1; i <= T; i++)
        up[i] = up[i - 1] + num[i];
    dp[0][0] = 1;
    int *pre = dp[0], *nxt = dp[1];
    for(int i = 1; i <= T; i++)
    {
        sum[0] = pre[0];
        for(int j = 1; j <= up[i]; j++)
            sum[j] = (sum[j - 1] + pre[j]) % 1000000;
        for(int j = 0; j <= up[i]; j++)
        {
            int tmp = max(0, j - num[i]);
            nxt[j] = (tmp == 0 ? sum[j] : (sum[j] - sum[tmp - 1] + 1000000));
            nxt[j] %= 1000000;
        }
        swap(nxt, pre);
    }
    int ans = 0;
    for(int i = S; i <= B; i++)
        ans = (ans + pre[i]) % 1000000;
    printf("%d\n", ans);
    return 0;
}