Drought (USACO Gold 2022 January)

这个题是比较hardcore的DP设计，主要是难点是状态不直观，然后最基础的解看不太清。

首先感觉上应该是一个DP的方向， $H$ ， $N$ 都比较小，也以复杂度应该就是 $O(HN)$ 之类。就是前 $i$ 的cow能有多少可行的组合，然后 $i=1..n$ 扩展。最简单的情况， $i=2$ 的时候，所有合法的状态都是两头牛的hunger level一样。

检查是否所有数字都能降到0，过程可以这样做：

for (i = [2..n] )
    h[i] -= h[i-1]
    assert(h[i] >= 0)
assert(h[n]==0)

如果要降到 $k$ ，可以把 $H[i]$ 预处理成 $H[i]-k$ ，就等价了。

所以我们的DP就是按这个过程来构造。 $\text{dp}[i][j]$ 表示前 $i$ 头牛的方案数，使得：
1. 前 $i-1$ 头牛饥饿值按上面代码可以降为0（按下面第四点，如果 $n$ 是奇数的时候，则是降到任意的 $k$ ）。
2. 第 $i$ 头牛饥饿值为 $j$ 。
$\text{dp}[i+1][j] = \sum \text{dp}[i][j'], 0 \leq j' \leq \min(H_i, H_{i+1}-j)$

$\text{dp}[1][j]=1$ , 求 $\text{dp}[N][0]$ 。
$n$ 为奇数和偶数的时候情况是不一样的，偶数时如果可以降到一样的值，则一定可以降到 $0$ ，所以我们只需要检查是否所有数字都能降到 $0$ 就可以了。奇数的时候，可能降到一个非 $0$ 的数字（可以证明这个数字是唯一的），所以我们需要用到上面的 $H[i]-k$ 的变换，让问题变成更容易解的“所有数字降到 $0$ ”的问题。
最简单的实现会发现TLE，最里层循环可以使用prefix sum，使用之后就AC了。

所以整个步骤是比较多的，难度比较大一些。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int H[105];     
int dp[105][1005];  // dp[i][j]，按上面伪代码，[0..i]中所有元素都降到0，最后一个是j的初始值数量
const int MOD = 1e9+7;
int ans;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &H[i]);
    
    int xmax = 0;
    if (n % 2) xmax = *min_element(H, H+n);
    for (int x = 0; x <= xmax; x++) {
        int ps[1005] = {0}, PS[1005];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= H[i]-x; j++) {
                if (i == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = H[i]-x-j > H[i-1]-x ? ps[H[i-1]-x] : ps[H[i]-x-j];
                    // 这个就是一个前缀和
                    // for (int k = 0; k <= H[i]-x-j; k++)
                    //     dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;
                }
                PS[j] = (j == 0 ? dp[i][j] : (PS[j-1]+dp[i][j]) % MOD);
            }
            swap(ps, PS);
        }
        ans = (ans + dp[n-1][0]) % MOD;
    }
    printf("%d", ans);
    return 0;
}