P6394 樱花，还有你 题解

HappyJaPhy · 2023-08-30 10:54:05 · 题解

P6394 题解

前言

• 超浪漫的原题
• 博客看文更佳

题意

• 在 n 种物品中，每种最多选择 s_i 个，问恰巧选出 m 个物品的方案数（一模一样的题目：摆花）。

分析

状态及转移的设计

• 这是一道很浪漫且经典的 DP 题。设 f_{i,j} 表示在第 i 颗树下正好收集到 j 朵樱花，初始状态 f_{0,0}=1。写出基本的转移方程： f_{i,j}=\sum_{l=j-s_i}^jf_{i-1,l}
• 就是这么简单（吗）！分析一下时间复杂度就能发现，这个做法是 O(nm^2) 的，只能通过 80\text{pts} 的分数。那该怎么办呢？
• 通过观察转移方程式可以发现，我们要求的 \sum 中的 f 是在连续区间内的！因此我们可以加入前缀和来优化转移，设 pre_{i,j} 表示 \sum_{k=1}^jf_{i,k}，于是就能将转移方程改为： f_{i,j}=pre_{i-1,j}-pre_{i-1,k-1}
• 这里 k=\max(0, j-s_i)。如果 k=0，那么就不用减去 pre_{i-1,k-1} 一项了（毕竟在某种程度上说，pre_{i-1,-1}=0）。并且，我们在计算 f 的同时就可以计算 pre（小卡常）。
• 注意：取模时两个 pre 相减可能出现负数，注意要判负！（别问我怎么知道）

上代码！

#include <bits/stdc++.h>
#define N 5003
#define mod 10086001
using namespace std;
int n, m, s[N], f[N][N], pre[N][N], ans;

inline void read(int &x) {
    char ch = x = 0;
    while (ch < '0' || ch > '9') {
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - 48;
        ch = getchar();
    }
    return ;
}

int main() {
    read(m), read(n);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        read(s[i]);
        sum += s[i];
    }
    if (sum < m) { //判断 IMP
        printf("impossible");
        return 0;
    }
    f[0][0] = 1; //初始状态 
    for (int i = 0; i <= m; i++) { //注意要提前赋值 
        pre[0][i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            int minn = max(j - s[i], 0);
            f[i][j] = pre[i - 1][j];
            if (minn) f[i][j] -= pre[i - 1][minn - 1]; //计算转移 
            while (f[i][j] < 0) f[i][j] += mod; //解决出现负数的情况 
            pre[i][j] = f[i][j];
            if (j) pre[i][j] = (pre[i][j] + pre[i][j - 1]) % mod;
        }
    }
    for (int i = 1; i <= n; i++) { //统计答案 
        ans = (ans + f[i][m]) % mod;
    }
    printf("%d", ans);
    return 0;
}

• 但是嘛……

空间优化

• 经过两次提交后我才发现（好吧我眼睛确实有点问题）——这题他只给了 64.00\text{MiB} 的空间！（卡不了时间就狂卡空间是吧？）
• 接下来就该考虑空间上的优化了。让我们再次看看 f 的转移方程还有 pre 的计算方程： f_{i,j}=pre_{i-1,j}-pre_{i-1,k-1}\\ pre_{i,j}=pre_{i,j-1}+f_{i,j} \end{array}
• 可以发现，所有的方程都只与 i 和 i-1 上的变量有关！因此我们就可以压缩掉第一维（注意：f 在计算时是要用到之前的 pre 的，因此我们需要把 f 和 pre 分开计算，避免覆盖）。
• 这时就有人要问了：“那你最后统计答案怎么办？这道题在每棵树下都能结束啊？”那就每个 f_m 算完就统计答案啊！（摇头叹气状）（这不废话嘛）

AC code

#include <bits/stdc++.h>
#define N 5003
#define mod 10086001
using namespace std;
int n, m, s[N], f[N], pre[N], ans;

inline void read(int &x) {
    char ch = x = 0;
    while (ch < '0' || ch > '9') {
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - 48;
        ch = getchar();
    }
    return ;
}

int main() {
    read(m), read(n);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        read(s[i]);
        sum += s[i];
    }
    if (sum < m) { //判断 IMP
        printf("impossible");
        return 0;
    }
    f[0] = 1;
    for (int i = 0; i <= m; i++) {
        pre[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            int minn = max(j - s[i], 0);
            f[j] = pre[j];
            if (minn) f[j] -= pre[minn - 1];
            while (f[j] < 0) f[j] += mod; //计算转移并判负 
        }
        pre[0] = f[0];
        for (int j = 1; j <= m; j++) {
            pre[j] = (f[j] + pre[j - 1]) % mod; //先计算 f 后计算 pre
        }
        ans = (ans + f[m]) % mod; //直接统计答案 
    }
    printf("%d", ans);
    return 0;
}

• 感谢能阅读到这里的各位！如有错误，欢迎指出！