题解 | #[CQOI2007]涂色PAINT#

[CQOI2007]涂色PAINT

http://www.nowcoder.com/practice/512619bee5874e85bd2812a0c9066125

考虑区间,设表示将区间染色需要的最少染色次数, 然后我们考虑如何将区间合并,由于我们对于一段连续的区间可以在一次内涂完, 这就意味着如果我们就可以直接从和位置的答案里转移过来。 否者,我们就要枚举断点,将区间分为两部分染色,并将两部分的结果相加,取最小的。 具体转移方程如下:

alt

alt

alt

#include <stdio.h>

int main()
{
    char s[51];
    int dp[51][51]={[0 ... 50]={[0 ... 50]=100}};
    gets(s);
    int len = strlen(s);
    for(int length=1;length<=len;++length)
    {
        for(int l=0;l<len;++l)
        {
            int r = l+length-1;
            if(r > len)
                break;
            if(l == r)
            {
                dp[l][r]=1;
                continue;
            }
            if(s[l] == s[r])
                dp[l][r] = dp[l+1][r] < dp[l][r-1] ? dp[l+1][r] : dp[l][r-1];
            else
                for(int k=l;k<r;++k)
                    dp[l][r] = (dp[l][k]+dp[k+1][r]) < dp[l][r] ? (dp[l][k]+dp[k+1][r]) : dp[l][r];
        }
    }
    printf("%d",dp[0][len-1]);

    return 0;
}
全部评论

相关推荐

昨天 11:21
门头沟学院 Java
总包48.5w,意想不到的价格
无情咸鱼王的秋招日记之薛定谔的Offer:R
点赞 评论 收藏
分享
10-27 17:26
东北大学 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务