Codeforces 1114D(区间DP）

题面

传送门

分析

法1（区间DP）：

首先，我们可以把连续的相等区间缩成一个数，用unique来实现，不影响结果

{1,2,2,3,3,3,5,3,4}->{1,2,3,5,3,4}

先从一个极端情况来考虑，a={1,2,3,4,5},此时答案显然为4，从1个点出发，先把它变成和左边的点相等，再把它变成和右边的点相等,一共需n-1次

假设我们已经把中间某个区间[i,j]变成相同颜色的一段,如{1,5,5,5,5,4}

如果a[i-1]!=a[j+1],则需要变两次,如果a[i-1]=a[j+1]，只需要变一次了，

所以我们需要求出形如a[i-1]=a[j+1]的数对个数ans，由于每个这样的数对会少变一次

所以答案就是n-1-ans

那么如何求出ans呢

区间DP，(dp[i][j])表示区间([i,j])外的数对个数

则(dp[i][j]=egin{cases} max(dp[i-1][j],dp[i][j+1]) \ max(dp[i-1][j],dp[i][j+1],dp[i-1][j+1]+1),a[i-1]=a[j+1]end{cases})

初始值(dp[1][n])=0

最后得到的(dp[i][i])表示除了i之外的数列中的数对个数，即从i开始变需要变n-1-(dp[i][i])次

取(dp[i][i])的最大值即可

时间复杂度(O(n^2))

---

法二（CF官方题解的做法）：

由法一的分析，我们注意到数对会形成回文子序列

如{1,3,2,5,3,1},则1 3 2 3 1就形成了回文子序列，

显然变化次数为n-(回文子序列长度+1)/2

因此我们只要求出最长的回文子序列长度，可以把原串和反串跑LCS，时间复杂度(O(n^2))

用LCS转LIS可以优化到(O(nlog n))

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 5005
using namespace std;
int n;
int a[maxn];
int dp[maxn][maxn];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	n=unique(a+1,a+1+n)-a-1;
	dp[1][n]=0;
	for(int len=n-1;len>=1;len--){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			dp[i][j]=max(dp[i-1][j],dp[i][j+1]);
			if(i-1>=0&&j+1<=n&&a[i-1]==a[j+1]) dp[i][j]=max(dp[i][j],dp[i-1][j+1]+1);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,dp[i][i]);
	printf("%d
",n-1-ans);
}