题解 | #[CQOI2007]涂色PAINT#
[CQOI2007]涂色PAINT
http://www.nowcoder.com/practice/512619bee5874e85bd2812a0c9066125
描述
给一个长度为的空字符串，每次选定一个子串染色，问将字符串染成目标颜色的最小次数
思路
- 经典的区间dp的题目，设表示将区间染成目标颜色的最小花费，转移方程为
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=55;
int dp[MAXN][MAXN];
char s[MAXN];
int main()
{
scanf("%s",s+1);
int n=strlen(s+1);
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++)
dp[i][i]=1;
for(int len=2;len<=n;len++)
for(int i=1;i<=n-len+1;i++)
{
if(s[i]==s[i+len-1])
dp[i][i+len-1]=min(dp[i+1][i+len-1],dp[i][i+len-2]);
for(int j=i;j<i+len;j++)
dp[i][i+len-1]=min(dp[i][i+len-1],dp[i][j]+dp[j+1][i+len-1]);
}
printf("%d\n",dp[1][n]);
}
时间复杂度，空间复杂度
投递叮咚买菜等公司7个岗位
小米三面63人在聊