关于$O(m*\sum a)$的做法,y总讲得很清楚了。
考虑进一步优化:
在原本的转移方程中(i已略去)
for(ll j=m;j;--j)
for(ll k=1;k<=a;++k)
if(j-k>=0)
f[j]=(f[j]+f[j-k])%mod;
注意到对于$j$而言,所有$p<j的f[p]$不会被$j$影响,且2-4行可表示为$$f[j]+=\sum _{p=max(0,j-a)}^{j-1} f[p]$$
所以,对于每次枚举$i$,我们预处理$f$的前缀和$s$,将上式改写为$$f[j]+=s[j-1]-s[j-a-1]$$
即可在$O(nm)$的时间内解决本题(注意要防止$j-a-1<0$导致越界RE)
code:
#include<iostream>
#include<cstdio>
typedef long long ll;
#define MAXN 2011
ll f[MAXN],s[MAXN];
const ll mod=1000007;
int main()
{
ll n,m;
scanf("%lld%lld",&n,&m);
f[0]=1;
for(ll i=1;i<=n;++i)
{
s[0]=1;
for(ll j=1;j<=m;++j)s[j]=s[j-1]+f[j];
ll a;
scanf("%lld",&a);
for(ll j=m;j>0;--j)
if(j-a>0)f[j]=(f[j]+s[j-1]-s[j-a-1])%mod;
else f[j]=(f[j]+s[j-1])%mod;
}
printf("%lld",f[m]);
return 0;
}
非常棒的题解!
感谢捧场!(您们是怎么知道我发了题解啊)
首页不是有最新通知吗
Orz,我都没怎么看这个
非常棒的题解!
感谢捧场!(但您为什么不玩AC Saber啊)
我玩了啊.