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)。

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

*/