A simple Blog for wyx I've been down the bottle hoping.
BZOJ 1055 [HAOI2008]玩具取名
发表于: | 分类: Oi | 评论:0 | 阅读:45

题意还是比较清晰的。大概 这题乍一看挺难,结果仔细一看数据范围就变成水题了

区间 $dp$ 当然可以,但是我们希望有更好写的方法,不妨利用记忆化搜索……

其实都一样,开始的时候智障了 ,以为都减去 $i$ 就变成了$0123$ 了

简单说一下记忆化怎么搜,当 $able(l,j,a)$ & $able(j,r,b)$ & $able(a,b)$

就说明 $(l,r)$ 可以变成我们想要的 $(a,b)$ 了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 200+50
using namespace std;
char p[5]="WING";
int hash[N],t[4];;
char str[N],a[4][20][2];
int f[N][N][4];
bool DFS(int l,int r,int k)
{
    if(l==r)
        return (str[l]==p[k]);
    int &res=f[l][r][k];
    if(res!=-1)return res;
    for(int i=1;i<=t[k];i++)
        for(int j=l;j<=r-1;j++)
            if(DFS(l,j,hash[a[k][i][0]])&&DFS(j+1,r,hash[a[k][i][1]]))
                return res=1;
    return res=0;
}
int main()
{
    memset(f,-1,sizeof(f));
    hash['W']=0;hash['I']=1;hash['N']=2;hash['G']=3;
    for(int i=0;i<4;i++)
        scanf("%d",t+i);
    for(int i=0;i<4;i++)
        for(int j=1;j<=t[i];j++)
            scanf("%s",a[i][j]);
    scanf("%s",str+1);
    int n=strlen(str+1);
    bool flag=0;
    for(int i=0;i<4;i++)
        if(DFS(1,n,i))
            flag=1,printf("%c",p[i]);
    if(!flag)
        puts("The name is wrong!");
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP