P1077 摆花

题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共盆。通过调查顾客的喜好，小明列出了顾客最喜欢的种花，从到标号。为了在门口展出更多种花，规定第种花不能超过盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。

输入格式

第一行包含两个正整数和，中间用一个空格隔开。
第二行有个整数，每两个整数之间用一个空格隔开，依次表示。

输出格式

一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对取模的结果。

输入输出样例

输入
2 4
3 2
输出
2

说明/提示

【数据范围】

对于20%数据，有；

对于50%数据，有；

对于100%数据，有。

NOIP 2012 普及组 第三题

解题思路

可以考虑动态规划，定义状态表示前种花占有前个位置的方案数，那么可以看出只与（前种花占有前个位置的方案数）有关，此处的即为第种花可能的摆放数量。
可得状态转移方程：

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]) % M;

可以得到c++代码

#include <iostream>

#define M 1000007
#define ll long long
using namespace std;
const int maxn = 101;
ll dp[maxn][maxn];
int a[maxn];

int main() {
    int n, m;
    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]) % M;

    cout << dp[n][m];
}

DP优化利用滚动数组，降低内存消耗

#include <iostream>

#define M 1000007
using namespace std;
const int maxn = 101;
int dp[2][maxn], a[maxn], t;

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    dp[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        t = 1 - t;
        for (int j = 0; j <= m; j++){
            dp[t][j] = 0;
            for (int k = 0; k <= min(a[i], j); ++k)
                dp[t][j] = (dp[t][j] + dp[1 - t][j - k]) % M;
        }
    }
    cout << dp[t][m];
}

DP优化 转变为一维动态规划，01背包问题
问题可以看作从盆花按顺序排列，挑选出盆的方案数。
表示长度为的子序列有多少种.

#include <iostream>

#define M 1000007
using namespace std;
const int maxn = 101;
int dp[maxn], a[maxn];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = m; j >=0; --j)//倒序，防止使用到已经处理过的dp[j - k]
            for (int k = 1; k <= min(a[i], j); ++k)
                //前i盆花可以取到j位置的方案数
                dp[j] = (dp[j] + dp[j - k]) % M;
    cout << dp[m];
}

搜索方法深度优先遍历

//来自：https://www.luogu.com.cn/blog/chenzhengyv/ti-xie-p1077-bai-hua-post
#include<bits/stdc++.h>
using namespace std;
const int maxn=105, mod = 1000007;
int n, m, a[maxn];
int dfs(int x,int k)
{
    if(k > m) return 0;
    if(k == m) return 1;
    if(x == n+1) return 0;
    int ans = 0;
    for(int i=0; i<=a[x]; i++) ans = (ans + dfs(x+1, k+i))%mod;
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    cout<<dfs(1,0)<<endl;
    return 0;
}

记忆化搜索

//来自：https://www.luogu.com.cn/blog/chenzhengyv/ti-xie-p1077-bai-hua-post
#include<bits/stdc++.h>
using namespace std;
const int maxn=105, mod = 1000007;
int n, m, a[maxn], rmb[maxn][maxn];
int dfs(int x,int k)
{
    if(k > m) return 0;
    if(k == m) return 1;
    if(x == n+1) return 0;
    if(rmb[x][k]) return rmb[x][k]; //搜过了就返回
    int ans = 0;
    for(int i=0; i<=a[x]; i++) ans = (ans + dfs(x+1, k+i))%mod;
    rmb[x][k] = ans; //记录当前状态的结果
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    cout<<dfs(1,0)<<endl;
    return 0;
}