【BZOJ】1260: [CQOI2007]涂色paint区间dp

Description

假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。用尽量少的涂色次数达到目标。

Input

输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。

Output

仅一行，包含一个数，即最少的涂色次数。

Sample Input

Sample Output

【样例输入1】 AAAAA 【样例输入1】 RGBGR 【样例输出1】 1 【样例输出1】

3

 题解：

  大约这个题就是给你一个序列，每次可以选择一个颜色覆盖一个区间，问最少多少次可以覆盖掉区间

  大约就是先枚举左端点，再枚举区间长度，然后判断一下如果区间两个端点的字符串的值是否相等，如果相等，说明可以由一个覆盖的刷子直接刷出来。剩下的枚举断点就好。

  还是再熟悉一下vs吧。。

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 51; int dp[MAXN][MAXN]; char c[MAXN]; int main(int argc, char *argv[]) { int T, n, m; int i, j, k, l; scanf("%s", c + 1); n = strlen(c + 1); memset(dp, 0x7f, sizeof(dp)); for (i = 1; i <= n; i++) dp[i][i] = 1; for (l = 1; l < n; l++) for (i = 1; i < n; i++) { j = i + l; if (j > n) break; if (c[i] == c[j]) { if (j == i + 1) dp[i][j] = 1; else { dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]); dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + 1); } } else { for (k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]); } } } printf("%d\n", dp[1][n]); return 0; }