题解：P12687 [KOI 2022 Round 1] 鹅卵石

true_kun · 2025-06-11 23:20:45 · 题解

设 dp_i 表示拿走 1 到 i 的所有石子需要的最少步数。

显然进行操作 2 如果可以使拿走全部石子，这将会使我们拿石子的步数变少，优化选石子的过程。我们暴力的去寻找一个 j，使得 j 到 i 这一段可以只通过操作 2 来拿走全部石子。

则有转移：

如何判断是否可以只通过操作 2 来拿走全部石子呢？我们考虑操作 2 拿走的石子数量与左边或者右边有关，如果我们从最右侧（即 i）开始向左推进 2 过程，则因为将右侧的点全部拿光，所以一个点拿走后只会对左边的点产生贡献。因为只使用操作 2 拿光，并且希望只用 i-j 次，所以经过一次操作 2 后当前点的石子数应该为 0，那么这个点左边的点的石子数就应该减去当前点石子数（与当前点一起拿走），如果这个点左边的石子数没有这个点的石子数大，那么当前点由于右侧已经没有石子了，其必定不能只通过过程 2 清空，其左边的区间自然也就不必考虑了。

代码见下：

#include<bits/stdc++.h>
using namespace std;
int dp[2505],a[2505],b[2505];//考虑到第i个位置，i前面的所有数都被拿走的最小步数 
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        int point=1;
        dp[i]=dp[i-1]+1;
        for(int j=1;j<=i;j++)b[j]=a[j];
        for(int j=i;j>=1;j--){
            b[j-1]-=b[j];
            if(b[j-1]<0){point=j;break;}
        }
        for(int j=point;j<=i;j++){
            if(b[j]==0)dp[i]=min(dp[i],dp[j-1]+i-j);
        }
    } 
    cout<<dp[n];
    return 0;
}