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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1055】【HAOI2008】【玩具取名】  

2014-03-17 15:59:28|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     = = 看着vfk君的动态仙人掌这种东西感觉自己实在是各种弱啊...
     = = 看着wshjzaa君的线性规划感觉自己弱透了....
     题目:论200长度的字符串一次可以把一对字符转化成一个字符最后能否变成长度为1的字符?
     第一个想法,区间DP... 设f[i][j] 表示它能转换成的字符连成的字符串,然后每一次枚举字符串里的字符即可。最后答案输出f[1][n]代表的字符串排序后的结果即可。由于数据太小了,所以怎么乱搞都可以额....不过还有一种更好写的写法,那就是设f[i][j][k]其中k是第k个字符,表示含义是f[i][j][k]能否合成WING的第K个。然后bool变量显然好写一点。
==================================================

program bzoj1055;
const maxn=210;
var f:array[0..maxn,0..maxn,0..4]of boolean;
    num:array[1..4]of longint;
    w:array[0..4,0..30]of string;
    flag:boolean;

function cal(ch:char):longint;
begin
  case ch of
  'W':exit(1);
  'I':exit(2);
  'N':exit(3);
  'G':exit(4);
  end;
end;

function cal(ch:longint):char;
begin
  flag:=false;
  case ch of
  1:exit('W');
  2:exit('I');
  3:exit('N');
  4:exit('G');
  end;
end;

procedure init;
var i,j,k,l,ww,m:longint;
    s:string;
begin
  for i:=1 to 4 do
   read(num[i]);
  readln;
  for i:=1 to 4 do
   for j:=1 to num[i] do
    readln(w[i][j]);
  readln(s);
  m:=length(s);
  fillchar(f,sizeof(f),false);
  for i:=1 to m do
    f[i][i][cal(s[i])]:=true;
  for j:=2 to m do
   for i:=1 to m-j+1 do
     for k:=i to i+j-2 do
       for l:=1 to 4 do
         for ww:=1 to num[l] do
          f[i][i+j-1][l]:=f[i][i+j-1][l]
          or (f[i][k][cal(w[l][ww][1])] and f[k+1][i+j-1][cal(w[l][ww][2])]);
  flag:=true;
  for i:=1 to 4 do
   if f[1][m][i] then
    write(cal(i));
  if flag then write('The name is wrong!'); 
end;

begin
  init;
end.





    
  评论这张
 
阅读(129)| 评论(2)

历史上的今天

评论

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

页脚

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