首页 > 分享 > NOip 2012 摆花

NOip 2012 摆花

花匠小妙招
2025-09-21 23:10

这道题比较简单，我也就不多赘述，相信在座各位都能看我的代码就能题目弄懂，所以本题提供两种解法，动态规划没有学好的同学可以看看递推的写法。

先上个动态规划的：

#include<stdio.h> #include<stdlib.h> #include<string.h> // 摆花类动态规划的背包问题或整数划分 /* ans[n][m]表示 n种花，放置到 m 个盆中可能的情况总数 DP方程： ans[i][j]=sum{ ans[i-1][j-x] } 0<=x<=min(num[i],j) */ int main() {int n,m,i,j,k,x;int num[101],ans[101][101];memset(ans,0,sizeof(ans));scanf("%d%d",&n,&m);for(i=1;i<=n;i++) scanf("%d",num+i);ans[0][0]=1; // 初始值0种花放置到0个盆子里，只有一种情况 //ans[1][1]=1; // 初始值1种花放置到1个盆子里，只有一种情况 ,若初始值设置了这种情况 // 在下面 ans[i][j]=ans[i][j]+ans[i-1][j-x]; 累加时，ans[1][1] 会多增加1，ans[1][1]变成2，造成结果错误for(i=1;i<=n;i++) for(j=0;j<=m;j++) { if(j>num[i]) k=num[i]; else k=j; for(x=0;x<=k;x++) ans[i][j]=(ans[i][j]+ans[i-1][j-x])%1000007; } //printf("%dn",sizeof(ans)); printf("%dn",ans[n][m]); }

然后再来个递推的：

#include<stdio.h> #include<stdlib.h> //[NOIP2012] 摆花 int n,m,i,p,l,temp,kind[101]={0}; long long k[101][101]={0};//递推存放，n种花放m个盆子种的可能情况种类 int main() { //freopen("flower.in","r",stdin); //freopen("flower.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=n;i++) scanf("%d",&kind[i]);for(i=0;i<=kind[1];i++) k[1][i]=1;//在zhi[1]的范围内，摆i盆花只有一种情况for(i=2;i<=n;i++)//枚举花的种类for(p=0;p<=m;p++)//枚举要摆的盆数{if(p<kind[i]) temp=p;else temp=kind[i];for(l=0;l<=temp;l++)//枚举当前种类花能添加的盆数 { k[i][p]+=k[i-1][p-l];//在有i种花,p盆花情况下，情况等于当前的情况,加上只有i-1种花，p-l盆花的情况 k[i][p]%=1000007; }}printf("%lldn",k[n][m]);return 0; }