- 题目考点:区间dp
- 题目大意:将一个空白模板涂成目标颜色的模板,一次涂色的长度任意,求最少涂色次数,参考题目样例:
例如第一次把木版涂成RRRRR,第二次涂成RGGGR,第三次涂成RGBGR,达到目标。
- 题目分析:用dp[ i ] [ j ] 表示从i涂到j所需要的最少涂色次数,则有以下两种情况:
-
第一种情况:
a [ i ] 和 a [ j ]颜色相同,如NIUKEN,则这种情况和涂NIUKE需要次数相同,因为我们可以在涂第一个N的时候一下涂到第二个N,两边颜色相同可以看成其中一个端点是拓展来的;
即 dp [ i ] [ j ] = dp [ i + 1 ] [ j ] , dp [ i ] [ j - 1 ]
第二种情况:两边颜色不相同,则我们可以把模板看成两块: -
则然l到r的最少次数就是(左边模板染色最少次数)+(右边模板染色最少次数)
- 即dp[ i ] [ j ] = dp [ i ] [ k ] + dp [ k + 1 ] [ j ]
代码如下:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 55;
char a[N];
int dp[N][N];
int main()
{
scanf("%s", a + 1);
int n = strlen(a + 1);
memset(dp, 0x3f, sizeof dp);
for(int i = 1; i <= n; i++)dp[i][i] = 1; //从i涂到i需要1次
for(int len = 2; len <= n; len++) //区间dp套路:长度由短到长实现状态转移
for(int i = 1; i + len - 1 <= n; i++) //对于每个长度,枚举区间起点
{
int l = i, r = i + len - 1;
if(a[l] == a[r]) //两端相同
dp[l][r] = min(dp[i+1][r], dp[i][r-1]);
else //两端不同
for(int j = l; j <= r; j++)
dp[l][r] = min(dp[l][r], dp[l][j] + dp[j+1][r]);
}
printf("%d", dp[1][n]); //输出从1 染色到n所需最少次数
return 0;
}
a [ i ] 和 a [ j ]颜色相同还是不太理解