poj 2138 Travel Games

题目链接：http://poj.org/problem?id=2138

题目思路：水题，先预处理出每两个串是否可达即可。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
vector<int>v[82];
vector<int>vt[1010];
int dp[1010];
char s[1010][110];
int rec[1010];
bool judge(char s1[],char s2[])
{
    int len1=strlen(s1);
   // int len2=strlen(s2);
    int i=0,j=0;
    while(s2[j])
    {
        if(s1[i]==s2[j])
        {
            i++,j++;
        }
        else
            j++;
        if(j-i>1)
            break;
    }
    if(i==len1)
        return true;
    else
        return false;
}
void dfs(int u)
{
    int i;
    if(dp[u]!=-1)
        return;
    dp[u]=0;
    rec[u]=u;
    for(i=0;i<vt[u].size();i++)
    {
        dfs(vt[u][i]);
       // dp[u]=max(dp[u],dp[vt[u][i]]+1);
       if(dp[vt[u][i]]+1>dp[u])
            dp[u]=dp[vt[u][i]]+1,rec[u]=rec[vt[u][i]];
    }
}
int main()
{
    int i,j,m,k;
    int len,maxn=3;
    scanf("%d%s",&m,s[0]);
    len=strlen(s[0]);
    v[len].push_back(0);
    memset(dp,-1,sizeof(dp));
    for(i=1;i<=m;i++)
    {
        scanf("%s",s[i]);
        len=strlen(s[i]);
        maxn=(len>maxn)?len:maxn;
        v[len].push_back(i);
    }
    for(i=3;i<maxn;i++)
    {
        for(j=0;j<v[i].size();j++)
        {
            for(k=0;k<v[i+1].size();k++)
            {
                if(judge(s[v[i][j]],s[v[i+1][k]]))
                {
                    vt[v[i][j]].push_back(v[i+1][k]);
                 //   printf("a\n");
                  //  printf("i %d j %d\n",v[i][j],v[i+1][k]);
                }
            }
        }
    }
    dfs(0);
    printf("%s\n",s[rec[0]]);
}