题解：CF2133D Chicken Jockey

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

在这

CPP

// 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 ;
}

题解：CF2133D Chicken Jockey

文章操作

Solution

Code

相关推荐

评论

题解：CF2133D Chicken Jockey