首页 > 代码库 > BZOJ 1260 [CQOI2007]涂色paint（区间DP）
BZOJ 1260 [CQOI2007]涂色paint（区间DP）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1260
【题目大意】
假设你有一条长度为n的木版，初始时没有涂过任何颜色
每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色
求最少的涂色次数达到目标状态
【题解】
dp[i][j]表示涂抹i到j的最优答案，
显然当i和j相同时，可以从i+1……j,i……j-1,i+1……j-1转移过来，
同时也可以从两个区间组合得到。
【代码】
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N=100;int dp[N][N];char s[N];int main(){ while(~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 k=1;k<n;k++){ for(int i=1;i<=n-k;i++){ if(s[i]==s[i+k]){ dp[i][i+k]=min(dp[i][i+k-1],dp[i+1][i+k]); dp[i][i+k]=min(dp[i][i+k],dp[i+1][i+k-1]+1); }else{ for(int j=i;j<i+k;j++){ dp[i][i+k]=min(dp[i][i+k],dp[i][j]+dp[j+1][i+k]); } } } }printf("%d\n",dp[1][n]); }return 0;}BZOJ 1260 [CQOI2007]涂色paint（区间DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。