P8096 [USACO22JAN] Drought G

· · 题解

由于按了 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;
}