poj3046+时间优化+空间优化dp(挑战)

给定t个数字，每个数字有Ni个，问凑出L~R区间数有多少？？

这题时间优化使用挑战里面的方程，空间的话就是滚动数组

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int Maxn=1e5+10;
const int INF=0x3f3f3f3f;
const LL MOD=1e6;
LL dp[3][Maxn];
int a[Maxn];
int ()
{
	int t,n,l,r,x;
	while(~scanf("%d%d%d%d",&t,&n,&l,&r))
	{
		memset(a,0,sizeof(a));
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
			scanf("%d",&x),a[x]+=1;

		LL *cur=dp[0],*nex=dp[1];
		cur[0]=1;
		for(int i=0;i<=t;i++)
		{
			nex[0]=1;
			for(int j=1;j<=n;j++)
			{
				if(j-1-a[i]>=0)
					nex[j]=(nex[j-1]+cur[j]-cur[j-1-a[i]]+MOD)%MOD;
				else
					nex[j]=(nex[j-1]+cur[j])%MOD;
			}
			swap(cur,nex);
		}

		LL ans=0;
		for(int i=l;i<=r;i++)
			ans=(ans+cur[i])%MOD;
		printf("%I64dn",ans);
	}
	return 0;
}