【涂色 —— 区间dp】

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int a[N], f[N][N];int main()
{int n;cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];if(a[i] == a[i-1]){i--;n--;}}for(int len = 2; len <= n; len++){for(int i = 1; i + len - 1 <= n; i++){int j = i + len - 1;if(a[i] == a[j]) f[i][j] = f[i+1][j-1] + 1;else f[i][j] = min(f[i+1][j], f[i][j-1]) + 1;}}cout << f[1][n];return 0;
}

思路

预处理

将颜色相同的元素合并，更新n值

状态定义

 表示从第 i 个元素到第 j 个元素涂成相同颜色的方法集合

 的值等于集合中方案的的最小值

目标状态

状态转移

首先明确扩展的过程中，联通块自然是连续的一段，而最后一步就是我们转移的讨论点、子集的划分点

若端点元素颜色不同，则联通块不论是另一个端点还是非端点元素的颜色，都与最后一个端点元素颜色不同，必然要耗费一次步骤

若端点元素颜色相同，则多出一种情况，就是最后一次将两个端点元素同时联通。

比较以下这三个方案的表达式可知，上面这个表达式就是考虑完全后最好的方案(第三个方案的子段是前两个子段的一部分)