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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1055][HAOI2008]玩具取名  

2014-11-12 20:10:01|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1055: [HAOI2008]玩具取名

一开始以为是双向广搜什么的……
后来一看变换数<=16就放弃了
忘记判无解结果WA了一次= =、
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 5;
const int M = 200+10;
int n,m;
int len[N],map[N][N][N],two[N]={0,1,2,4,8};
char bh[100],str[M],out[N]={0,'W','I','N','G'};
int f[M][M];
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
int i,j,a,b,c,k;
char cc;
n = 4;
bh['W'] = 1;
bh['I'] = 2;
bh['N'] = 3;
bh['G'] = 4;
for(i=1;i<=n;i++)len[i] = scan();
for(i=1;i<=n;i++){
for(j=1;j<=len[i];j++){
scanf(" %c",&cc);a = bh[cc];
scanf(" %c",&cc);b = bh[cc];
map[a][b][i] = 1;
//printf("%d %d %d\n",a,b,i);
}
}
scanf("%s",str+1);
len[0] = strlen(str+1);
//printf("%s\n",str+1);
for(i=1;i<=len[0];i++){
f[i][i] = two[bh[str[i]]];
//printf("%d ",f[i][i]);
}
for(j=2;j<=len[0];j++)
for(i=1;i+j-1<=len[0];i++){
int l,r;
l = i;r = i+j-1;
for(k=1;k<j;k++){

for(a=1;a<=n;a++)
if(f[l][l+k-1]&two[a])
for(b=1;b<=n;b++)
if(f[l+k][r]&two[b])
for(c=1;c<=n;c++)
if(map[a][b][c])
f[l][r] |= two[c];
}
}
/*
printf("%d %d\n",f[1][2],f[3][4]);
printf("%d %d\n",f[1][1],f[2][4]);
printf("%d\n",f[1][4]);*/
if(f[1][len[0]] == 0){printf("The name is wrong!");return 0;}
for(i=1;i<=n;i++)
if(f[1][len[0]] & two[i]){
printf("%c",out[i]);
}
return 0;
}

题解:
区间DP
f[i][j]表示区间[l,r]可以缩成哪些字符
f[i][j]从f[i][k],f[k+1][j](i≤k<j)转移过来,每次转移是4^3
总时间复杂度是O(n^3*4^3)
  评论这张
 
阅读(111)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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