【BZOJ1630/2023】[Usaco2007 Demo]Ant Counting

题意：T中蚂蚁，一共A只，同种蚂蚁认为是相同的，有一群蚂蚁要出行，个数不少于S，不大于B，求总方案数

题解：DP，先列出朴素的方程，用f[i][j]表示前i种，出行j只的方案数，v[i]代表第i中蚂蚁的个数

f[i][j]=∑f[i-1][j-k] (0≤k≤min(j,v[i]))

也可以表示为

f[i][j]=∑f[i-1][k] (j-min(j,v[i])≤k≤j)

发现时间复杂度为均摊O(A^2)，那么我们可以用前缀和优化，空间复杂度为O(T*A)，我们可以采用滚动数组

关于数据范围什么的，反正O(T*A)过了，题目描述233

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#define mod 1000000

using namespace std;

int f[2][100010],s[2][100010];

int n,m,l,r;

int v[100010];

int main()

{

    int i,j,k,a;

    scanf("%d%d%d%d",&n,&m,&l,&r);

    for(i=1;i<=m;i++)

    {

        scanf("%d",&a);

        v[a]++;

    }

    for(i=0;i<=m;i++)    s[0][i]=1;

    for(i=1;i<=n;i++)

    {

        for(j=0;j<=m;j++)

        {

            if(j<=v[i])    f[i&1][j]=s[(i&1)^1][j];

            else    f[i&1][j]=(s[(i&1)^1][j]-s[(i&1)^1][j-v[i]-1]+mod)%mod;

            if(!j)    s[i&1][j]=f[i&1][j];

            else    s[i&1][j]=(s[i&1][j-1]+f[i&1][j])%mod;

        }

    }

    printf("%d",(s[n&1][r]-s[n&1][l-1]+mod)%mod);

    return 0;

}

【BZOJ1630/2023】[Usaco2007 Demo]Ant Counting DP的相关教程结束。