CF2133D Chicken Jockey 题解

个人感觉 D 比 C 简单很多。

题目大意我就不描述了，直接跳到讲解。

考虑 DP。定义

dp_i

表示处理第

1

个到第

i

个骑士的最小攻击次数。

我们想一下如何转移。

首先就是最后攻击

i

，答案为

dp_{i-1}+(a_i-1)

。注意，当前

i-1

个结束时，

i

会下落，血量减一。

然后还有一种方案，就是攻击

i-1

使得

i

下落。答案为

dp_{i-2}+a_{i-1}+(a_i-(i-1))

。注意这里的

a_i-(i-1)

可能小于

0

，处理一下即可。

两中方案取最小值即可，时间复杂度

O(n)

。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
int n;
int a[N];
int dp[N];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	dp[0]=0;
	dp[1]=a[1];
	for(int i=2;i<=n;i++){
		dp[i]=dp[i-1]+(a[i]-1);
		dp[i]=min(dp[i],dp[i-2]+a[i-1]+max(0ll,a[i]-i+1));
	}
	cout<<dp[n]<<"\n";
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T=1;
	cin>>T;
	while(T--)solve();
	return 0;
}
/*

*/

CF2133D Chicken Jockey 题解

文章操作

相关推荐

评论

CF2133D Chicken Jockey 题解