POJ 3046 Ant Counting

POJ_3064

    这个题可以直接用生成函数的思路去做，但如果我们用f[i][j]表示到第i种蚂蚁时选了j个蚂蚁的方案种数进行dp的话，还可以得到时间复杂度更优的算法。

    同时，这个题目让我意识到了取模运算（%）耗时确实比较长，用得越少越好……

//生成函数

#include<stdio.h>
#include<string.h>
#define MAXD 1010
#define MAXM 100010
#define D 1000000
int h[MAXD], wa[MAXM], wb[MAXM], A, B, S, T, *a, *b;
void init()
{
    int i, j, k;
    memset(h, 0, sizeof(h[0]) * (T + 1));
    scanf("%d%d%d", &A, &S, &B);
    for(i = 0; i < A; i ++)
    {
        scanf("%d", &k);
        ++ h[k];
    }
}
void solve()
{
    int i, j, k, *t, ans = 0;
    a = wa, b = wb;
    memset(b, 0, sizeof(b[0]) * (B + 1));
    b[0] = 1;
    for(i = 1; i <= T; i ++)
    {
        memset(a, 0, sizeof(a[0]) * (B + 1));
        for(j = 0; j <= h[i]; j ++)
            for(k = 0; k + j <= B; k ++)
                a[k + j] = (a[k + j] + b[k]) % D;
        t = a, a = b, b = t;
    }
    ans = 0;
    for(i = S; i <= B; i ++)
        ans = (ans + b[i]) % D;
    printf("%d\n", ans);
}
int main()
{
    while(scanf("%d", &T) == 1)
    {
        init();
        solve();
    }
    return 0;
}

//dp
#include<stdio.h>
#include<string.h>
#define MAXD 1010
#define MAXM 100010
#define D 1000000
int h[MAXD], wa[MAXM], wb[MAXM], A, B, S, T, *a, *b;
void init()
{
    int i, j, k;
    memset(h, 0, sizeof(h[0]) * (T + 1));
    scanf("%d%d%d", &A, &S, &B);
    for(i = 0; i < A; i ++)
    {
        scanf("%d", &k);
        ++ h[k];
    }
}
void solve()
{
    int i, j, k, *t, ans = 0;
    a = wa, b = wb;
    memset(b, 0, sizeof(b[0]) * (B + 1));
    b[0] = 1;
    for(i = 1; i <= T; i ++)
    {
        k = 0;
        for(j = 0; j <= B; j ++)
        {
            if(j - h[i] > 0)
                k -= b[j - h[i] - 1];
            k = (k + b[j] + D) % D;
            a[j] = k;
        }
        t = a, a = b, b = t;
    }
    ans = 0;
    for(i = S; i <= B; i ++)
        ans = (ans + b[i]) % D;
    printf("%d\n", ans);
}
int main()
{
    while(scanf("%d", &T) == 1)
    {
        init();
        solve();
    }
    return 0;
}