首页 > 代码库 > 【动态规划】Gym - 100507G - The Debut Album
【动态规划】Gym - 100507G - The Debut Album
一般思路的dp是用f(i,j,0)表示前i位最后有j个1的方案数，用f(i,j,1)表示前j位最后有j个2的方案数，j都是大于等于1的，然后比较容易转移。
但这题卡内存，就只能用f(i,j)表示前i位最后有j个1的方案数，这里j大于等于0。
然后转移就略麻烦，自己看代码领会一下吧。
也可以看成是滚动数组优化。
#include<cstdio>
using namespace std;
#define MOD 1000000007
int n,lim[2];
int f[50010][310],g[50010];
int main()
{
//freopen("g.in","r",stdin);
scanf("%d%d%d",&n,&lim[0],&lim[1]);
f[1][0]=f[1][1]=1;
g[1]=1;
for(int i=2;i<=n;++i)
{
for(int k=1;k<=lim[0] && k<=i;++k)
{
f[i][k]=(f[i][k]+f[i-1][k-1])%MOD;
g[i]=(g[i]+f[i][k])%MOD;
}
for(int k=1;k<=lim[1] && k<=i-1;++k)
f[i][0]=(f[i][0]+g[i-k])%MOD;
if(i<=lim[1])
f[i][0]=(f[i][0]+1)%MOD;
}
int ans=0;
for(int k=0;k<=lim[0] && k<=n;++k)
ans=(ans+f[n][k])%MOD;
printf("%d\n",ans);
return 0;
}
【动态规划】Gym - 100507G - The Debut Album
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。