Mix and Build(簡易DP)

Mix and Build Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 3936 Accepted: 1203 Case Time Limit: 2000MS Special Judge
Description In this problem, you are given a list of words (sequence of lower case letters). From this list, find the longest chain of words w1, …, wn such that wi is a mixed extension of wi-1. A word A is a mixed extension of another word B if A can be formed by adding one letter to B and permuting the result. For example, “ab”, “bar”, “crab”, “cobra”, and “carbon” form a chain of length 5.
Input The input contains at least two, but no more than 10000 lines. Each line contains a word. The length of each word is at least 1 and no more than 20. All words in the input are distinct.
Output Write the longest chain that can be constructed from the given words. Output each word in the chain on a separate line, starting from the first one. If there are multiple longest chains, any longest chain is acceptable.
Sample Input
ab arc arco bar bran carbon carbons cobra crab crayon narc
Sample Output
ab bar crab cobra carbon carbons
Source Rocky Mountain 2004の簡単なDpは、最も長い文字列チェーンを探して、後の1つを前の1つの長さより大きくして、1つの文字だけが異なるようにします

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;

typedef unsigned long long LL;

const int MAX = 1e5+10;

struct node
{
    char str[25];
    int Hash[26];
    int len;
    int Dp;
    int pre;
    void init()// 
    {
        memset(Hash,0,sizeof(Hash));
        len=0;
        Dp=1;
        pre=-1;
    }
    void HASH()// 
    {
        len=strlen(str);
        for(int i=0;i<len;i++)
        {
            Hash[str[i]-'a']++;
        }
    }
    void Output()
    {
        printf("%s
",str);
    }
}Ch[11000];

bool cmp(node a,node b)// 
{
    return a.len<b.len;
}

void DFS(int s)// 
{
    if(s==-1)
    {
        return ;
    }
    DFS(Ch[s].pre);
    Ch[s].Output();
}

int main()
{
   // freopen("input.txt","r",stdin);
    for(int i=0;i<10001;i++)
    {
        Ch[i].init();
    }
    int top=0;
    while(~scanf("%s",Ch[top].str))
    {
        Ch[top].HASH();
        top++;
    }
    sort(Ch,Ch+top,cmp);
    for(int i=0;i<top;i++)
    {
        for(int j=i-1;j>=0;j--)
        {
            if(Ch[j].len==Ch[i].len)
            {
                continue;
            }
            if(Ch[j].len==Ch[i].len-1)
            {
                int ans=0;
                for(int k=0;k<26;k++)
                {
                    if(Ch[i].Hash[k]!=Ch[j].Hash[k])
                    {
                        ans++;
                    }
                    if(ans>2)
                    {
                        break;
                    }
                }
                if(ans<2)// 
                {
                    if(Ch[i].Dp<Ch[j].Dp+1)
                    {
                        Ch[i].Dp=Ch[j].Dp+1;
                        Ch[i].pre=j;
                    }
                }
            }
            else
            {
                break;
            }
        }
    }
    int Max=0,ans;
    for(int i=0;i<top;i++)
    {
        if(Max<Ch[i].Dp)
        {
            Max=Ch[i].Dp;
            ans=i;
        }
    }
    DFS(ans);
    return 0;
}