本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-10 17:05:45

题目分析

对序列 $a_1,a_2,...a_n$ 来说，只有连续的相等序列段才需要修改。

对于第 $i$ 个元素来说，只可能因为与左侧相等被修改一次，与右侧相等被修改一次，最多修改次数为两次。

因此，第 $i$ 个元素是否被修改只与第 $i-1$ 个元素相关，可以用动态规划解决该问题。

设 $dp_{i,0/1/2}$ 表示当前点被修改的次数。

当某个 $k$ 满足 $a_i+j \neq a_{i-1}+k$ 时，转移方程为 $dp_{i,j}=\min(dp_{i,j},dp_{i-1,k}+b_i\times j)$。

边界条件

我们要求最小值，所以 $dp$ 数组要初始化为最大值。

初始条件为 $dp_{0,0}=dp_{0,1}=dp_{0,2}=0$ .

参考代码

#include<bits\/stdc++.h>
using namespace std;
const int N=2e5+9;
typedef long long ll;
ll a[N],b[N],dp[N][3],n;\/\/对当前数来说f[i][0\/1]表示变了自己增加了多少，最多加2。 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
	\/\/可以分类讨论，感觉不如dp好写，dp可以无脑暴力枚举 
	
	memset(dp,0x3f,sizeof(dp)) ;
	a[0]=-2e9;
	dp[0][0]=dp[0][1]=dp[0][2]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<3;j++)
			for(int k=0;k<3;k++)
				if(a[i]+j!=a[i-1]+k) dp[i][j]=min(dp[i][j],dp[i-1][k]+j*b[i]);	
	} 
	cout<<min(dp[n][0],min(dp[n][1],dp[n][2]));
}