自动搬运

查看原文

来自洛谷，原作者为

	耶梦加得 In the end it doesn't even matter.

搬运于2025-08-24 22:35:56，当前版本为作者最后更新于2022-02-07 16:48:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

由于按了 Command+Q 导致没能晋级的选手报到

大眼观察，$H_i$ 这么小，复杂度很可能和 $H_i$ 有关，然后 $N$ 也很小，所以复杂度很可能是 $O(HN),O(HN^2),O(H^2N)$ 之类的。又是有限制的，“答案可能很大”的计数，八成是 DP 没跑了。

显然我们有一个状态是“当前处理到第 $i$ 头牛”。考虑从 $i$ 到 $i+1$ 的转移过程，容易发现此时 $[1,i-1]$ 的牛应当都处于同一饥饿值，否则无论如何对 $i + 1$ 操作都无法满足条件。

也就是说，还有两个状态分别是牛 $i$ 的饥饿值 $j$，以及牛 $[1,i-1]$ 的饥饿值 $k$。空间 $O(NH^2)$，爆炸。

仔细考虑，容易发现其实我们只关心这两个值的差值。对于整个 DP 过程而言 $k$ 的值一旦确定就无法改变。我们可以将 DP 分若干次次进行，每一次人为规定每一头奶牛最终的饥饿值为 $k$。设 $\min\{H_i\} = M$，易知 $k \le M$。对于每一次 DP，先把所有 $H_i$ 都减去 $k$。

那么规定 $dp[i][j]$ 表示前 $i$ 头牛使得：

1. 前 $i - 1$ 头牛饥饿值为 0（注意：在减去 $k$ 的意义下）;
2. 第 $i$ 头牛饥饿值为 $j$。

考虑转移，由于考虑 $dp[i + 1][j]$ 的时候我们要把第 $i$ 头牛也喂饱，也就是对于 $dp[i][j']$，要先对 $i, i+1$ 两头牛投喂 $j'$ 次，因此 $j' + j \le H_{i + 1}$。容易得到转移方程：

$dp[i + 1][j] = \sum{dp[i][j']}(0 \le j \le \min(H_i,H_{i+1}-j)$

边界为 $dp[1][j] = 1$，要求 $dp[N][0]$。

可以通过处理前缀和的方式 $O(1)$ 转移，DP 复杂度 $O(NH)$，总复杂度 $O(NH^2)$，空间上可以通过滚动数组进一步优化（代码没有用滚动数组）。

最后输出 $dp[N][0]$ 的总和然后发现样例都过不去，交一发 WA50。

对于样例 $2$ 输出 $dp$ 数组，发现我们第一次 DP 就得出了 $dp[N][0] = 137$。

冷静分析题目，发现题目问的是有多少种初始情况，而不是有多少种方案。当 $N$ 为偶数时，$k$ 为多少不重要（可以通过 $N/2$ 次操作变成 $k-1$），因此我们对于这种情况进行一次 DP 后直接输出 $dp[N][0]$ 即可。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
inline int mmin(register int x, register int y) {
    return x > y ? y : x;
}
const long long mod = 1000000007;
int n;
int a[107], mn = 1000;
long long ans, g[107][1007];
signed main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        mn = mmin(mn, a[i]);
    }
    for(int i = 0; i <= a[1]; ++i) g[1][i] = i + 1; //这里省略了求和
    if(n % 2 == 0)mn = 0;
    for(int d = 0; d <= mn; ++d) {
        for(int i = 2; i <= n; ++i) {
            g[i][0] = g[i - 1][mmin(a[i], a[i - 1]) - d];
            for(int j = 1; j <= a[i] - d; ++j) {
                g[i][j] = g[i][j - 1] + g[i - 1][mmin(a[i] - j, a[i - 1]) - d];
                if(g[i][j] >= mod) g[i][j] -= mod;
            }
        }
        ans += g[n][0]; if(ans >= mod) ans -= mod;
    }
    printf("%lld\n", ans);
    return 0;
}