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]=\begin{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(n\log 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",n-1-ans);

}

巴特西

Codeforces 1114D(区间DP）

题面

分析

代码

最新文章

热门文章