题解：CF2133D Chicken Jockey

convie · 2025-08-25 10:07:30 · 题解

对于此题，考虑到每次切割当前元素会使后面一个元素收到它前面元素的个数的伤害，而切割后的后部分的元素我们不需要在其内部进行切割，也就是对于后部分，我们只能对其进行消灭，因为如果后部分的元素还要切割的话，那么一定是在此之前进行切割更优，对于逐个消灭的操作，每个元素除第一个外都会收到一点伤害。

因此，没有后效性可以想到 dp ，用 dp[i][1] 表示当前点进行切割，用 dp[i][0] 表示当前点不进行切割。

 dp[i][0]=min(dp[i+1][1],dp[i+1][0])+a[i]-(i!=1);

表示当前点不进行切割，那么操作数就是当前元素的生命值减去掉落的一点伤害以及后一个元素的操作最小值。

dp[i][1]=min(dp[i+2][1],dp[i+2][0])+max(0ll,a[i+1]-i)+a[i];

表示当前元素进行切割，受影响的只有后面一个元素。 完整代码如下。

const int INF=1e18;
int a[MAXN];
int dp[MAXN][2];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n+5;i++)
    dp[i][0]=dp[i][1]=INF;
    dp[n+1][0]=dp[n+1][1]=dp[n+2][1]=dp[n+2][1]=0;
    for(int i=n;i>=1;i--){
        dp[i][0]=min(dp[i+1][1],dp[i+1][0])+a[i]-(i!=1);
        dp[i][1]=min(dp[i+2][1],dp[i+2][0])+max(0ll,a[i+1]-i)+a[i];
        // cout<<i<<" "<<dp[i][0]<<" "<<dp[i][1]<<endl;
    }
    cout<<max(dp[1][0],dp[1][1])<<endl;
}
signed main(){
    // ios;
    int t=1;
    cin>>t;
    // cout<<fixed<<std::setprecision(15);
    while(t--)
    solve();
    return 0;
}