题解：CF2133D Chicken Jockey

SunJude · 2025-08-25 22:37:06 · 题解

Solution

首先考虑最简单的情况，每次只杀栈底的怪物：

对于第 1 个怪：需要 h_1 刀。
对于第 i(i \geq 2) 个怪：在第 i - 1 个怪死后，它会掉 1 点坠落伤害，于是就需要 \max(0, h_i - 1) 刀。

此时的答案是 \textrm{base} = h_1 + \sum_{i = 2} ^{n} \max(0, h_i - 1)。

然后我们考虑提前杀掉第 i(i \leq n - 1) 只怪的收益。

对于第 i 只怪：本来需要 h_i - 1 刀，现在需要 h_i 刀，收益为 -1。
对于第 i + 1 只怪：本来需要 \max(0, h_{i + 1} - 1) 刀，现在需要 \max(0, h_{i + 1} - i) 刀，收益为两者相减。

则净收益为 \Delta_i = \max(0, h_{i + 1} - 1) - \max(0, h _{i + 1} - i) - 1。

很自然地，我们想到 dp。但如果直接 dp 的话是有后效性的。多个位置一起提前杀，收益显然不是直接相加，而是会彼此影响。

这时候注意到一个结论：两个相邻的位置不能都被提前杀掉，否则一定不优。

证明：我们假设把 i 和 i + 1 都提前杀掉（记作 \texttt{A}），证明其一定劣于只提前杀 i + 1（记作 \texttt{B}）。

显然其只会影响到 i, i + 1, i + 2，我们分别来考虑。

对于 i：\texttt{A} 需要 h_i 刀，\texttt{B} 现在需要 h_i - 1 刀，\texttt{A} 比 \texttt{B} 多打 1 刀。
对于 i + 1：\texttt{A} 和 \texttt{B} 相同，都是 h_{i + 1} 刀。
对于 i + 2：对于 \texttt{A}，由于 i 已经被杀掉了，所以杀 i + 1 时 i + 2 下面有 i 个怪；对于 \texttt{B}，杀 i + 1 时 i + 2 下面有 i + 1 个怪。

则 \texttt{A} 比 \texttt{B} 多打的刀数为 \max(0, h_{i + 2} - i) - \max(0, h_{i + 2} - (i + 1)) \in \{0, 1\}。

综上，\texttt{A} 比 \texttt{B} 多打 1 或 2 刀，所以 \texttt{A} 劣于 \texttt{B}。

证毕。

令 v_i = \max(0, \Delta_i)，问题转化为：选不相邻的若干位置使得 \sum v_i 最大。

于是就变成了简单 dp！设 \textrm{dp}_{i, 1/0} 表示到 i 为止且选/不选 i 的最大收益。转移是简单的。

\textrm{dp}_{i, 0} = \max(\textrm{dp}_{i - 1, 0}, \textrm{dp}_{i - 1, 1}) \\ \textrm{dp}_{i, 1} = \textrm{dp}_{i - 1, 0} + v_i

最后答案就是 \textrm{base} - \max(\textrm{dp}_{n - 1, 0}, \textrm{dp}_{n - 1, 1})。

Code

::::info[在这]

// Problem: D. Chicken Jockey
// Contest: Codeforces - Codeforces Round 1044 (Div. 2)
// URL: https://codeforces.com/contest/2133/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long 
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define ls x << 1
#define rs x << 1 | 1

using namespace std;

const int maxn = 2e5 + 5;

int n, h[maxn] ;
int v[maxn] ;
int f[maxn][2] ;

void solve(){
    cin >> n ;
    v[1] = 0 ;
    rep(i, 1, n) f[i][0] = f[i][1] = 0 ;
    rep(i, 1, n) cin >> h[i] ;
    int base = h[1] ;
    rep(i, 2, n) base += max(0ll, h[i] - 1) ;
    rep(i, 2, n - 1) {
        int delta = max(0ll, h[i + 1] - 1) - max(0ll, h[i + 1] - i) - 1 ;
        v[i] = max(0ll, delta) ;
    }
    rep(i, 1, n - 1) {
        f[i][0] = max(f[i - 1][0], f[i - 1][1]) ;
        f[i][1] = f[i - 1][0] + v[i] ;
    }
    cout << base - max(f[n - 1][0], f[n - 1][1]) << endl ;
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1 ; 
    cin >> T ;
    while(T -- ){
        solve() ;
    }
    return 0 ;
}

::::