POJ 2564:Edit Step Ladders
1972 ワード
浅談\(Trie\):https://www.cnblogs.com/AKMer/p/10444829.html
テーマ転送ゲート:http://poj.org/problem?id=2564
記\(f[i]\)は、\(i\)番目の文字列からどれぐらいの長さに変換できるかを示します。
現在の文字列を\(Trie\)ツリーで検索するたびに、\(dp(ID,u,len,bo)\)を設定して表示します。\(ID\)番目の文字列を\(Trie\)ツリー上で検索して、\(u\)という点で、すでに\(len\)ビットを処理しました。
修正は次の文字以外のところに行って検索を続け、列挙\(26\)バーを挿入して逐次検索しますが、\(len\)を追加せず、削除は再度現在のノードにアクセスします。\(len=len+1\)
「(len\)が文字列の長さに等しい場合と、現在の点が示すあの号文字列の\(f_{u}+1\)は\(max\)を取ればいいです。
答えは\(f\)の最大値にプラスします。
時間複雑度:\((n*len^2*26)\)
空間複雑度:\(O(n*len*26)\)
コードは以下の通りです
テーマ転送ゲート:http://poj.org/problem?id=2564
記\(f[i]\)は、\(i\)番目の文字列からどれぐらいの長さに変換できるかを示します。
現在の文字列を\(Trie\)ツリーで検索するたびに、\(dp(ID,u,len,bo)\)を設定して表示します。\(ID\)番目の文字列を\(Trie\)ツリー上で検索して、\(u\)という点で、すでに\(len\)ビットを処理しました。
修正は次の文字以外のところに行って検索を続け、列挙\(26\)バーを挿入して逐次検索しますが、\(len\)を追加せず、削除は再度現在のノードにアクセスします。\(len=len+1\)
「(len\)が文字列の長さに等しい場合と、現在の点が示すあの号文字列の\(f_{u}+1\)は\(max\)を取ればいいです。
答えは\(f\)の最大値にプラスします。
時間複雑度:\((n*len^2*26)\)
空間複雑度:\(O(n*len*26)\)
コードは以下の通りです
#include
#include
#include
using namespace std;
const int maxn=25005;
int n=1,ans;
char s[maxn][20];
int f[maxn],Len[maxn];
struct Trie {
int tot;
int id[maxn*16];
int son[maxn*16][26];
void ins(int ID) {
int pos=1,len=strlen(s[ID]+1);
for(int i=1;i<=len;i++) {
if(son[pos][s[ID][i]-'a'])
pos=son[pos][s[ID][i]-'a'];
else pos=son[pos][s[ID][i]-'a']=++tot;
}
id[pos]=ID;
}
void dp(int ID,int u,int len,int bo) {
if(len==Len[ID]) {
if(id[u]&&bo)return;
if(id[u])f[ID]=max(f[ID],f[id[u]]+1);
if(bo) {
for(int i=0;i<26;i++)
if(id[son[u][i]])f[ID]=max(f[ID],f[id[son[u][i]]]+1);
}
return;
}
int c=s[ID][len+1]-'a';
if(son[u][c])dp(ID,son[u][c],len+1,bo);
if(bo) {
for(int i=0;i<26;i++) {
dp(ID,son[u][i],len,0);
if(i!=c)dp(ID,son[u][i],len+1,0);
}
dp(ID,u,len+1,0);
}
}
}T;
int main() {
T.tot=1;
while(~scanf("%s",s[n]+1))n++;
for(int i=1;i
転載先:https://www.cnblogs.com/AKMer/p/10446925.html