题目传送门

题意

题目大意： 放 $m盆花在一排，总共有 $n种花，编号为 $i的花最多能放 $a[$i]盆，摆放时同一种花要放一起，且花的编号要从小到大。

思路：

解析

一、暴力

直接暴力搜索得到结果，骗30分。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 105;
const int mod = 1e6 + 7;
LL n, m, a[N];
LL dfs(int k, int p){    //k为第几种花，p为几盆花 
    if (p == m) return 1;
    if (k > n || p > m) return 0;
    LL ans = 0;
    for (int i = 0; i <= a[k]; i++)
        ans = (ans + dfs(k + 1, p + i)) % mod;
    return ans;
}
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    cout << dfs(1, 0) << "\n";
    return 0;
}

二、记忆化搜索

暴力超时，于是想到通过记忆化减少时间，100分。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 105;
const int mod = 1e6 + 7;
LL n, m, num[N][N], a[N];
LL dfs(int k, int p){    //k为第几种花，p为几盆花 
    if (p == m) return 1;
    if (k > n || p > m) return 0;
    if (num[k][p]) return num[k][p];
    LL ans = 0;
    for (int i = 0; i <= a[k]; i++)
        ans = (ans + dfs(k + 1, p + i)) % mod;
    num[k][p] = ans;
    return ans;
}
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    cout << dfs(1, 0) << "\n";
    return 0;
}

三、dp

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 1e6 + 7;
const int N = 105;
LL n, m, f[N][N], a[N];
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= a[i]; k++)
                if (j >= k)
                    f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
    cout << f[n][m] % mod << "\n";
    return 0;
}