题解：P1077 [NOIP2012 普及组] 摆花

曾经刚学 dp 时做的题现在能交题解了，写篇纪念一下吧。

题意

给定 n 种花，每种花的上限是 a_i，求摆放 m 盆花的方案数（同种花放一起，按编号从小到大摆放，结果对 1000007 取模）。

思路

设 dp_{i,j} 为考虑前 i 种花，摆放 j 盆花的方案数。

但是如何判断这是道 dp 题呢？算法标签。

但是你打比赛的时候是没有算法标签的，所以在这讲一下如何判断 dp 。

• 依赖性
  • 动态规划的核心思想是将一个复杂问题分解成一系列相互重叠的子问题，也就是 dp 的一个重要性质 —— 子任务依赖性！
  • 例如在本题中，计算 dp_{i,j} 时，需要用到 dp_{i-1,j-k} 的值，其中 k 的取值范围是 0 到 \min(a_i,j)。这意味着，计算 dp_{i,j} 的过程，会依赖于之前计算过的 dp_{i-1,...} 的结果。

• 无后效性

  • dp 的另一个性质是无后效性。无后效性是指，在推导后面阶段的状态时，我们只需要关心上一个阶段的状态，而不需要关心前面阶段是如何达到这个状态的。也就是说，一旦某个状态的值确定了，它就不会受到后续决策的影响。
  • 在本题中计算 dp_{i,j} 时，我们只关心 dp_{i-1,j-k} 的值，而不关心 dp_{i-1,j-k} 的值是如何计算出来的。只要它的值是正确的，我们就可以用它转移 dp_{i,j}。

综上，本题适合用动态规划解决。

考虑如何转移。

对于第 i 种花，可以摆放 k 盆 ( 0 \le k \le \min (a_i, j) )。

因此，当计算 dp_{i,j} 时，可以累加前 i-1 种花摆放 j-k 盆的方案数，也就是 dp_{i,j} = \sum dp_{i-1,j-k}。

细节：

• 初始化 dp_{0,0}=1：不放花，0 盆的方案数是 1。
• 结果 dp_{n,m}：所有花都考虑，摆放 m 盆花的方案数。
• 注意取模。

Code

#include <iostream>
#include <algorithm>
using namespace std;
const int MOD=1000007;
int dp[105][105];
int n,m;
int a[105];
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;++i) 
        cin>>a[i];
    dp[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=m;++j){
            for(int k=0;k<=min(a[i],j);++k) 
                dp[i][j]=(dp[i][j]+dp[i-1][j-k])%MOD;
        }
    }
    cout<<dp[n][m];
    return 0;
}

写题解不易，点个赞再走呗～