题解：B4428 [CSP-X2025 山东] 勇者斗恶龙

wflengxuenong · 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]));
}