题目大意
一排有n个方格，已知初始的颜色，现在按一定规则改变它们的颜色。
开始操作前，先选定一个方格x；再重复操作：将包含该方格的同色区域（一些连续的同色方格）全部改为一种颜色，直到所有方格同色。
如何选择方格可以使得操作重复次数最少？输出这个最小值。
思路
先把颜色相同的方格看成一个，生成一个新的数组bf[]，bf[]有cnt个元素。
- 选任意一个方格，cnt-1次操作一定可以完成；
- 对于某个方格，若其两边有一对颜色相同个方格，就可以少一次操作，将这一对方格及其中间的方格看作一个在往两边找，若还有方格，就又可以减少一次操作……（搜索的暴力方法就基本完善了）
- 把相同的颜色连上线，则对于每一个方格，横跨它，不相交的连线有多少条，就可以减少多少次操作。（如图，对于6，就有两条，红色和紫色）
动态规划的雏形大概就是：f[i][k]表示从第i个方格开始的看个方格中，最多可连线条数，那么
然而，TLE。考虑pre[i][k]表示 ，fore[i][k]表示 。似乎解决了，然而MLE。注意到只需保留pre[][k-2],pre[][k-1],pre[][k],fore[][k-2],fore[][k-1],fore[][k]所以还要用滚动数组。
最终的代码就是这样了。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=5001;
4 int n,f[N][N],bf[N],cnt,ans,pre[N][3],fore[N][3];
5
6 int main()
7 {
8 // freopen("in.in","r",stdin);
9 // freopen("2.out","w",stdout);
10 scanf("%d",&n);
11 cnt++;
12 scanf("%d",&bf[cnt]);
13 for(int i=2;i<=n;i++)
14 {
15 int tem;
16 scanf("%d",&tem);
17 if(tem!=bf[cnt])
18 {
19 cnt++;
20 bf[cnt]=tem;
21 }
22 }
23
24 for(int k=3;k<=cnt;k++)
25 {
26 for(int i=1;i<=cnt-k+1;i++)
27 {
28 f[i][k]=max(fore[i+k-2][(k-2)%3],max(pre[i+1][(k-2)%3],f[i][k]));
29 if(bf[i]==bf[i+k-1])f[i][k]++;
30 pre[i][k%3]=max(pre[i][(k-1)%3],f[i][k]);
31 fore[i+k-1][k%3]=max(fore[i+k-1][(k-1)%3],f[i][k]);
32 }
33 }
34 int ans=max(pre[1][cnt%3],fore[cnt][cnt%3]);
35 ans=cnt-1-ans;
36 printf("%d\n",ans);
37 return 0;
38 }