P4170 [CQOI2007] 涂色 题解

特殊情况：若 c[i] 表示 i 位置要求的颜色，若 c[l]=c[r] 会发生什么事呢？在 l 到 r-1 区间必然有一次操作将 l 到 k 的区间涂成了 c[l]，其中 l\le k \le r-1。那么把这次操作延伸到 r 不就多涂了一个 r 吗？注：并不会影响其他位置的颜色，其他操作会把 c[l] 覆盖掉！

喜闻乐见的代码时间

本码绝对是题解中最简短的！没有理解难度！

#include

using namespace std;

char c[55];int n=1,dp[55][55];

int main()

{

memset(dp,0x7f7f7f,sizeof(dp));

while(cin>>c[n])

{

dp[n][n]=1;n++;//初始化，长度为1的区间代价为1

}

n--;//千万别漏！

for(int i=1;i

{

for(int l=1;l<=n-i;l++)//枚举左端点

{

int r=l+i;//右端点

if(c[l]==c[r])dp[l][r]=min(dp[l+1][r],dp[l][r-1]);//特殊情况

for(int k=l;k

}

}

cout<

return 0;

}

完结撒花！感谢观看！