poj 3046 Ant Counting

 题目链接：http://poj.org/problem?id=3046

题目分类：动态规划+滚动数组优化

代码：

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>

using namespace std;

int s[2000];
int dp[3][100086];

int main()
{
    int t,n,a,b,sum;
    scanf("%d %d %d %d",&t,&n,&a,&b);
    memset(s,0,sizeof(s));
    for(int i=1;i<=n;i++)
    {
        int temp;
        scanf("%d",&temp);
        s[temp]++;
    }
    sum=0;

    dp[0][0]=1;
    for(int i=1;i<=t;i++)
    {
        sum+=s[i];
        memset(dp[i%2],0,sizeof(dp[i%2]));
        for(int k=0;k<=s[i];k++)
        {
            for(int j=sum;j>=k;j--)
            {
                dp[i%2][j]=(dp[i%2][j]+dp[(i-1)%2][j-k]);
                while(dp[i%2][j]>=1000000)
                    dp[i%2][j]-=1000000;
            }
        }
    }
    int ans=0;
    for(int i=a;i<=b;i++)
    {
       ans+= dp[t%2][i];
       while(ans>=1000000)
            ans-=1000000;
    }
    printf("%d
",ans);
}