P1077 摆花

_Wolverine_ · 2019-08-01 11:23:54 · 个人记录

设状态f[i][j]为用前i种花，在能摆j盆花的情况下摆花的方案数

其中j为第i种花摆的数量，k为前i-1种花已经摆的花的数量
第i种花摆了j种，所以摆第i种花之前的情况就是f[i-1][k]
所以得出动态转移方程：f[i][j+k]+=f[i-1][k]

枚举每种花可以摆的数量的所有可能性，在能摆出当前枚举到的数量的花的前提下，枚举前i-1盆花可能已经摆了多少盆：

for(int i=1;i<=n;++i)
{
    a=read();//读入第i种花最多可以放多少盆
    for(int j=0;j<=a;++j)//枚举花可以放的盆数
    for(int k=0;k<=m-j;++k)//枚举之前已经放了多少盆花
    {
        if(j==0 && k==0)continue;
        f[i][j+k]+=f[i-1][k];
        f[i][j+k]%=mod;
    }
}

AC代码：

#include<cstdio>

const int Maxn=110,mod=1000007;
int n,m,a;
int f[Maxn][Maxn];
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int main()
{
    n=read(),m=read();
    for(int i=0;i<=n;++i)
    f[i][0]=1;
    for(int i=1;i<=n;++i)
    {
        a=read();
        for(int j=0;j<=a;++j)
        for(int k=0;k<=m-j;++k)
        {
            if(j==0 && k==0)continue;
            f[i][j+k]+=f[i-1][k];
            f[i][j+k]%=mod;
        }
    }
    printf("%d\n",f[n][m] % mod);
    return 0;
}