1055: [HAOI2008]玩具取名

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1055

dp。d[i][j][k]表示i~j能否缩成字母k。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int MaxN=20;
const int MaxL=201;

int t[4],ch[4][MaxN][2],l;
bool d[MaxL][MaxL][4];

int change(char c)
{
    switch (c)
    {
        case 'W':
            return 0;
        case 'I':
            return 1;
        case 'N':
            return 2;
        case 'G':
            return 3;
    }
}

void init()
{
    memset(d,0,sizeof(d));
    for (int i=0;i<4;i++)
    {
        cin>>t[i];
    }
    for (int i=0;i<4;i++)
    {
        for (int j=0;j<t[i];j++)
        {
            char c[5];
            cin>>c;
            ch[i][j][0]=change(c[0]);
            ch[i][j][1]=change(c[1]);
        }
    }
    char c[201];
    cin>>c;
    l=strlen(c);
    for (int i=0;i<l;i++)
    {
        d[i][i][change(c[i])]=1;
    }
}

void dp()
{
    for (int length=2;length<=l;length++)
    {
        for (int i=0;i<l-length+1;i++)
        {
            for (int j=0;j<4;j++)
            {
                for (int k=i+1;k<=i+length-1;k++)
                {
                    for (int p=0;p<t[j];p++)
                    {
                        if (d[i][k-1][ch[j][p][0]]==1 && d[k][i+length-1][ch[j][p][1]]==1)
                        {
                            d[i][i+length-1][j]=1;
                            break;
                        }
                    }
                    if (d[i][i+length-1][j]==1)
                    {
                        break;
                    }
                }
            }
        }
    }
}

void write()
{
    bool flag=0;
    if (d[0][l-1][0]==1)
    {
        cout<<'W';
        flag=1;
    }
    if (d[0][l-1][1]==1)
    {
        cout<<'I';
        flag=1;
    }
    if (d[0][l-1][2]==1)
    {
        cout<<'N';
        flag=1;
    }
    if (d[0][l-1][3]==1)
    {
        cout<<'G';
        flag=1;
    }
    if (flag==0)
    {
        cout<<"The name is wrong!";
    }
    cout<<endl;
}

int main()
{
    init();
    dp();
    write();
    return 0;
}

posted on 2013-02-15 15:10 Kiro 阅读(113) 评论(0)  编辑 收藏 引用 所属分类: 衡八oj

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理