P4170-[CQOI2007]涂色
题目:
题目描述:
假设你有一条长度为 $5$ 的木版，初始时没有涂过任何颜色。你希望把它的 $5$ 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 $5$ 的字符串表示这个目标：RGBGR。
每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成 RRRRR，第二次涂成 RGGGR，第三次涂成 RGBGR，达到目标。
用尽量少的涂色次数达到目标。
输入格式:
输入仅一行，包含一个长度为 $n$ 的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。
输出格式:
仅一行，包含一个数，即最少的涂色次数。
样例:
样例输入1:
样例输出1:
样例输入2:
样例输出2:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include "ybwhead/ios.h"
const int maxn = 50;
int f[maxn][maxn];
int n;
int main()
{
string s;
yin >> s;
n = s.size();
for (int i = 1; i <= n; i++)
f[i][i] = 1;
for (int l = 1; l <= n; l++)
{
for (int j = l + 1; j <= n; j++)
{
int i = j - l;
f[i][j] = INT_MAX;
if (s[i - 1] == s[j - 1])
f[i][j] = min(f[i][j - 1], f[i + 1][j]);
else
for (int k = i; k < j; k++)
{
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
}
}
}
cout << f[1][n] << endl;
return 0;
}
|