题解：CF2153D Not Alone

· · 题解

求点赞 qwq！

用到的 trick 和 P17114 好像，题解。

思路

观察发现，若一个环形数组优美，则它可以被划分成若干段，每段内数值都相同，且每段的长度均 \ge 2。

可以得出，一个优美的环形数组可以拆成长度为 2 和 3 的段内数值都相同的段，也就是说我们想要让一个环形数组优美，把它拆成长度为 2 和 3 的段考虑即可。

发现由于是个环，不妨先弱化题目，假如 a 是个序列。

考虑连续的东西，dp 很好搞。

接下来考虑弱化版的 dp。

状态定义（弱化）

定义 dp_i 表示将序列 a_1,a_2,\dots,a_i 变成优美的最少操作次数。

定义这里的优美为能将序列 a_1,a_2,\dots,a_i 划分成若干长度为 2 和 3 的段，每段内数值都相同。

状态转移（弱化）

考虑最后一个段的长度。

所以：

dp_i=\min{\big(}dp_{i-2}+|a_i-a_{i-1}|,dp_{i-3}+\max({a_i,a_{i-1},a_{i-2}})-\min({a_i,a_{i-1},a_{i-2}})\big)

为防止越界，i>3。

边界（弱化）

显然 dp_1=\infty,dp_2=|a_2-a_1|,dp_3=\max(a_1,a_2,a_3)-\min(a_1,a_2,a_3)。

接下来再考虑环。

考虑环的情况，此时就是一个段跨过去了（即 a_1,a_n 在同一个段中考虑）。

那我们单独考虑这个段即可。

由于只用考虑段长度为 3 或者 2 的情况，那这个段可能是 a_n,a_1，或 a_n,a_1,a_2，或者 a_{n-1},a_n,a_1。

但是我们需要知道其它段需要的操作次数的最小值。

做三个 dp 即可。

状态定义

定义 dp_{x,i} 表示将 a_{x}\sim a_i 变成优美的最少操作次数，其中 1\le x\le 3。

状态转移

与弱化的状态转移差不多：

dp_{x,i}=\min{\big(}dp_{x,i-2}+|a_i-a_{i-1}|,dp_{x,i-3}+\max({a_i,a_{i-1},a_{i-2}})-\min({a_i,a_{i-1},a_{i-2}})\big)

为防止越界，i>x+2。

边界

显然 dp_{i,i}=\infty,dp_{i,i+1}=|a_{i+1}-a_i|,dp_{i,i+2}=\max(a_i,a_{i+1},a_{i+2})-\min(a_i,a_{i+1},a_{i+2})，其中 1\le i\le 3。

答案

正如上面所说，考虑所有的一个段跨过去的情况，与没有一个段跨过去的情况取最小值即可。

所以答案为：

\min{\big(}dp_{1,n},dp_{2,n-1}+|a_1-a_n|,dp_{2,n-2}+\max(a_n,a_{n-1},a_1)-\min(a_n,a_{n-1},a_1),dp_{3,n-1}+\max(a_n,a_2,a_1)-\min(a_n,a_2,a_1){\big)}

代码

时间复杂度 O(tn)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,INF=0x7f7f7f7f7f7f7f7f;
int t,n,a[N],dp[4][N];
int c(int x,int y,int z){return min({abs(x-y)+abs(x-z),abs(y-x)+abs(y-z),abs(z-x)+abs(z-y)});}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i],dp[1][i]=dp[2][i]=dp[3][i]=INF;
        dp[1][2]=abs(a[2]-a[1]),dp[1][3]=c(a[1],a[2],a[3]);
        for(int i=4;i<=n;i++)dp[1][i]=min(dp[1][i-2]+abs(a[i]-a[i-1]),dp[1][i-3]+c(a[i],a[i-1],a[i-2]));
        dp[2][3]=abs(a[3]-a[2]),dp[2][4]=c(a[2],a[3],a[4]);
        for(int i=5;i<=n;i++)dp[2][i]=min(dp[2][i-2]+abs(a[i]-a[i-1]),dp[2][i-3]+c(a[i],a[i-1],a[i-2]));
        dp[3][4]=abs(a[3]-a[4]),dp[3][5]=c(a[3],a[4],a[5]);
        for(int i=6;i<=n;i++)dp[3][i]=min(dp[3][i-2]+abs(a[i]-a[i-1]),dp[3][i-3]+c(a[i],a[i-1],a[i-2]));
        cout<<min({dp[1][n],dp[2][n-1]+abs(a[1]-a[n]),dp[2][n-2]+c(a[n],a[n-1],a[1]),dp[3][n-1]+c(a[n],a[2],a[1])})<<'\n';
    }
}