自动搬运

查看原文

来自洛谷，原作者为

	true_kun 高贵的初中生，没人三国杀（真_鸡-甄_姬）

搬运于2025-08-24 23:17:26，当前版本为作者最后更新于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;
}