目录
题目
p1077 摆花
思路
$text{dp}$
$text{f[i][j]}$表示前$i$种花摆了$j$盆的方案数。
设$x$($x$的范围为$[0,a_i]$)为第$i$种花摆了多少盆,$k$($k$的范围为$[0,m-x]$)为前面$i-1$种花摆了多少盆。枚举$x$,$k$。
所以$f[i][x+k]=f[i][x+k]+f[i-1][k]$
代码
#include<bits/stdc++.h> using namespace std; int n,m; int f[101][101]; inline int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; } int main(){ n=read(),m=read(); for(int i=0;i<=n;++i){ f[i][0]=1; } for(int i=1,num;i<=n;++i){ num=read(); for(int j=0;j<=num;++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]%=1000007; } } } printf("%dn",f[n][m]%1000007); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602313.html