注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1260][CQOI2007]涂色paint  

2015-01-13 21:29:53|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1260: [CQOI2007]涂色paint

白书原题……
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 50+10;
const int M = 27;
int n,m;
short f[N][N][M];
char str[N];
int main(){
//printf("%.3f\n",sizeof(f)/1024.0/1024);
int i,j,k,c,val = 26;
scanf("%s",str+1);
int len = strlen(str+1);
for(i=1;i<=len;i++)
for(j=1;j<=len;j++)
for(k=0;k<=val;k++)
f[i][j][k] = 2*len;
for(i=1;i<=len;i++){
str[i]=str[i]-'A'+1;
//printf("%d ",str[i]);
f[i][i][0] = 1;
f[i][i][str[i]] = 0;
}
//[i,i+j]
for(j=1;j<len;j++)
for(i=1;i+j<=len;i++){
int l = i,r = i+j,tmp[2];
for(c=0;c<=val;c++){
for(k=l;k<r;k++){
if(f[l][k][c] < f[l][k][0])tmp[0] = f[l][k][c];else tmp[0] = f[l][k][0];
if(f[k+1][r][c] < f[k+1][r][0])tmp[1] = f[k+1][r][c];else tmp[1] = f[k+1][r][0];
tmp[0] += tmp[1];
if(tmp[0] < f[l][r][c])f[l][r][c] = tmp[0];
}
if(f[l][r][c]+1 < f[l][r][0])f[l][r][0] = f[l][r][c]+1;
}
}
printf("%d\n",(int)f[1][len][0]);
return 0;
}

题解:
区间DP
倒着涂颜色,认为后涂的颜色在下面
f[i][j][c]表示区间中不涂颜色c所需的最小操作次数,f[i][j][0]表示全涂完所需的最小操作次数
然后每次转移是O(n)总时间复杂度是O(n^3 * 26)
  评论这张
 
阅读(100)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017