题解 P1077 【摆花】

这个题是一道典型的动态规划，即可以从之前的状态推出后面的状态的最优解。 这里我开了一个二维数组，$f[i][j]$指摆第$i$个花后总共摆了$j$盆的最优解。 每次摆花的循环要从$0$开始，到$t$结束（题中是$a[i]$），即摆放$t$盆第$i$种花。 这个状态可以由上一个$i$的$j$转移过来，其中$j+t$要小于$m$（$m$是最多摆放的花盆数）。为防止变量冲突，代码里用的是$k$。 ------------ 因为$i$总在$i-1$后面 则$DP$的状态转移方程为$f[i][j+k]+=f[i-1][k];$ 最后，不要忘了每做一次都要$mod1000007$，因为这个题不用$max,min$等函数，是从左向右推的过程，所以保险起见，在各个涉及$f$数组的地方都要$mod1000007$ ```cpp #include<cstdio> #include<cstring> #define mod 1000007 int max(int x,int y){return x>y?x:y;} int f[101][101];//f[i][j]指摆第i个花后总共摆j盆的最优解 int main() { int n,m,t; scanf("%d%d",&n,&m); memset(f,0,sizeof(f)); for(int i=0;i<=n;i++) f[i][0]=1; for(int i=1;i<=n;i++)//枚举到第i盆花 { scanf("%d",&t); for(int j=0;j<=t;j++)//第i盆花装j盆 for(int k=0;k<=m-j;k++)//从已经装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; } ``` ------------ 从这个题我才知道$DP$并不是全都有$max,min$函数的啊，$DP$的核心其实是从上一层的最优解推下一层的最优解，但这个题的最优即所有方案加起来的和，所以这个题没有取$max,min$。 #### 其实这个题的$DP$特点是比较强的。