题意
给定一个有颜色的砖块序列,每个数字表示一个颜色。任意选一个起始砖块,每次操作让包含起始砖块的连通块变成一种指定的颜色。求使得所有砖块颜色相同的最少操作数。
预处理
由于每次操作是处理一个连通块,那么可以把连通块用一个点表示,对点的操作等价于对连通块的操作
措施:对砖块的颜色序列去重
状态表示
依题意,把一个有颜色的砖块序列看作一个区间,比如原序列(1,2,3,4,5),那么可以看作区间[0,4],从该区间里任意选一个点(起始砖块),在满足题意的条件下进行操作,求让所有砖块颜色相同的最少操作数。
抽象出来
对于一个区间[i,j],从该区间任选一个点,在满足题意的条件下进行操作,求让所有砖块颜色相同的最少操作数。
把这个答案记作f[i,j],这就是状态
=>f[0,n-1]表示的是从区间[0,n-1]中任选一个起始砖块,最后操作成全部砖块颜色相同的最少操作数。
状态计算
第一大类:c[i]!=c[j]
由于只能以起始砖块为基准往两边扩展,所以,最后扩展到的一定是
左端点c[i]
与右端点c[j]
最后扩展的一步:有且仅有两个连通块,操作一次后变成一个连通块
1、最后扩到左端点:
此时一个连通块为ci,另外一个连通块是c[i+1~j],此时操作次数+1即可。操作+1的前提是c[i+1~j]已经是一个连通块了,此时又回到题目问的问题,对于区间(i+1~j)blabla…,就是f[i+1][j],所以操作总数为f[i+1][j]。
2、最后扩到右端点:
由于对称性,同理得,操作总数为f[i][j+1]第二大类:c[i]==c[j]
1、起点在左端点:
需要先从i扩展到j-1再扩展到j。第一步i扩展到j-1,并且要求最后一次扩展到j-1,由于这个要求,这个方案数属于集合(i,j-1)=>方案数>=f[i][j-1];然后再扩展到j,操作数+1,则总方案数>=f[i][j-1]+1
2、起点在右端点:
由对称性同理可知,总方案数>=f[i+1][j]+1
3、起点在左、右端点之间:
区间(i+1,j-1)的扩展无特殊要求,状态直接表示成f[i+1,j-1],最后同时扩到两个端点,方案书+1,总操作数为f[i+1][j-1]+1
比较可得第三种情况最优
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5010;
int f[N][N],c[N];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>c[i];
//由于每次操作都是对连通块操作,所以可以把每个连通块用一个点表示,对点的操作等价于对连通块的操作
int x=unique(c,c+n)-c;//去重后的长度,作为原始区间的长度,并且满足每一个点(连通块视为点)的颜色不同
for(int len=2;len<=x;len++)
for(int i=0;i+len-1<x;i++)
{
int j=i+len-1;
if(c[i]!=c[j]) f[i][j]=min(f[i+1][j],f[i][j-1])+1;
else f[i][j]=f[i+1][j-1]+1;
}
cout<<f[0][x-1];
}