C - Modern Art 3 G
题意
有一种画法：每次可以填一段区间，把一段区间填成相同的颜色，给你成品，问最少填了多少次。
思路
区间 dp，对于一段区间，显然会有一条分割线，把画作分成两边，如果没有，那就没意义了，考虑 DFS，对于一个区间，枚举分割线，我们发现必然能够找到一条分割线使得被截断的颜色的条数 \(\le 1\)，因为设区间 \([l, r]\) 那么我们知道 \(l, r\) 是这个区间的最左边和最右边，假设说找不到，那么必然有一条不是 \([l, r]\) 的一条颜色能够覆盖 \([l, r]\)， 那么区间就不应该是 \([l, r]\)，假设不成立，那么就只要考虑被截断的颜色条即可，那么我们可以得知这种颜色条必然是会覆盖 \([l, r]\) 之一的，所以只要判断 \(l, r\) 的颜色是否一样，如果一样就会被截断，否则就肯定有一条分割线可以不切断任意一条颜色条来分割两边，所以只要在统计答案是考虑一下这种情况即可，随后改 dp。
code
点击查看代码
#include <iostream>
using namespace std;
const int MaxN = 310;
int dp[MaxN][MaxN], a[MaxN], n;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int i = 1, x; i <= n; i++) {
cin >> a[i], dp[i][i] = 1;
}
for (int len = 2; len <= n; len++) {
for (int i = 1, j = i + len - 1; j <= n; i++, j++) {
dp[i][j] = 1e9;
for (int k = i; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] - (a[i] == a[j]));
}
}
}
cout << dp[1][n] << endl;
return 0;
}