POJ 2004 Mix and build Trieツリー?dp?
2883 ワード
Trie木の中で勉强しているので、インターネットでTrie木の问题を探して、これを见つけて、人は简単なdpだと书いていますが、私は何かTrie木の上のdpを勉强することができると思っていましたが、最后にTrie木と何の関系もないことに気づきました...
題意はあなたに多くの文字列(長さ<20)をあげて、それから2つの文字列が並べ替えた後に、左側の1つの+1つの文字が右になることができて、この2つの文字列は1つの辺につながって、それから最も長い辺を求めます.長いこと考えていたのにどうしてTrieと縁がないのか...1つの自然な考えはこのようにして、d[i]を連番iとする文字列を終了文字列の最長長として、私はまずすべての文字列を長さによって小さいから大きいまで並べ替えて、それから各文字列kに対して、私は毎回中の1つの文字を削除して、この新しい文字列jが存在しないことを見て、d[k]=max(d[k],d[j]+1)が存在するならば.それから一番大きいのをメモして、再帰的に印刷してください.Trieを使わなければならないなら、それは基本的な挿入検索機能を実現することであり、このハッシュはそれよりずっと速いかもしれないが、本当にmapもできない.でもTrieはmapより速いはずだ.これを勉強する以上、私は練習として手をつけましょう...最近この2,3日すべてRE..姿勢が悪いですね
題意はあなたに多くの文字列(長さ<20)をあげて、それから2つの文字列が並べ替えた後に、左側の1つの+1つの文字が右になることができて、この2つの文字列は1つの辺につながって、それから最も長い辺を求めます.長いこと考えていたのにどうしてTrieと縁がないのか...1つの自然な考えはこのようにして、d[i]を連番iとする文字列を終了文字列の最長長として、私はまずすべての文字列を長さによって小さいから大きいまで並べ替えて、それから各文字列kに対して、私は毎回中の1つの文字を削除して、この新しい文字列jが存在しないことを見て、d[k]=max(d[k],d[j]+1)が存在するならば.それから一番大きいのをメモして、再帰的に印刷してください.Trieを使わなければならないなら、それは基本的な挿入検索機能を実現することであり、このハッシュはそれよりずっと速いかもしれないが、本当にmapもできない.でもTrieはmapより速いはずだ.これを勉強する以上、私は練習として手をつけましょう...最近この2,3日すべてRE..姿勢が悪いですね
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#define maxn 10000
using namespace std;
struct StrNode
{
char sd[25];
char s[25];
int id;
bool operator < (const StrNode &b) const
{
return strlen(this->sd)<strlen(b.sd);
}
}str[maxn+50];
int d[maxn+50]; //
int prevv[maxn+50]; //
struct TrieNode
{
TrieNode *next[26];
int id;
}T[30*maxn],*Trie;
int trietop;
void insert(char *s,int idx)
{
int len=strlen(s);TrieNode *p=Trie;
for(int i=0;i<len;++i){
if(p->next[s[i]-'a']!=NULL){
p=p->next[s[i]-'a'];
}
else{
memset(T[trietop].next,0,sizeof(T[trietop].next));T[trietop].id=-1;
p->next[s[i]-'a']=&T[trietop++];
p=p->next[s[i]-'a'];
}
}
p->id=idx;
}
int find(char *s)
{
int len=strlen(s);TrieNode *p=Trie;
for(int i=0;i<len;++i){
if(p->next[s[i]-'a']!=NULL){
p=p->next[s[i]-'a'];
}
else{
return -1;
}
}
return p->id;
}
int query(char *s)
{
char tmp[25];int len=strlen(s);int cnt=0;
int ret=-1,maxd=-1;
for(int i=0;i<len;++i){
cnt=0;
for(int j=0;j<len;++j){
if(i!=j) tmp[cnt++]=s[j];
}
tmp[cnt]='\0';
int tret=find(tmp);
if(tret!=-1&&d[tret]>maxd){
ret=str[tret].id;
maxd=d[tret];
}
}
return ret;
}
void print(int x)
{
if(prevv[x]!=-1){
print(prevv[x]);
}
printf("%s
",str[x].s);
}
int main()
{
trietop=0;memset(T[trietop].next,0,sizeof(T[trietop].next));T[trietop].id=-1;Trie=&T[trietop++];
int n=0;char ins[25];memset(prevv,-1,sizeof(prevv));
while(scanf("%s",ins)!=EOF)
{
strcpy(str[n].sd,ins);
strcpy(str[n].s,ins);
sort(str[n].sd,str[n].sd+strlen(str[n].sd));
++n;
}
sort(str,str+n);for(int i=0;i<n;++i) str[i].id=i;
insert(str[0].sd,0);d[0]=0; int maxid=0,maxdist=0;
for(int i=1;i<n;++i){
int px=query(str[i].sd);
if(px!=-1){
d[i]=d[px]+1;prevv[i]=px;
if(d[i]>maxdist){
maxid=i;
maxdist=d[i];
}
}
else {
d[i]=0;
}
insert(str[i].sd,i);
}
print(maxid);
return 0;
}