問題描述

某人有一套玩具，并想法給玩具命名。首先他選擇WING四個字母中的任意一個字母作為玩具的基本名字。然后

他會根據自己的喜好，將名字中任意一個字母用“WING”中任意兩個字母代替，使得自己的名字能夠擴充得很長。 現在，他想請你猜猜某一個很長的名字，最初可能是由哪幾個字母變形過來的。 區間DP和記憶化 練習DP中。。代碼幾乎是照著題解寫的。 題解：http://hzwer.com/5333.html? 對代碼進行了一些補充說明 #include<bits/stdc++.h> using namespace std; char s[4]={'W','I','N','G'}; char a[4][20][2],ch[220]; int f[210][210][4]; int q[250],t[5]; bool flag; bool dp(int l,int r,int k){if(l==r){return ch[l]==s[k];}int &res=f[l][r][k];//為l到r的字母可不可以縮寫成k if(res!=-1)return res;for(int i=1;i<=t[k];i++){for(int j=l;j<=r-1;j++){if(dp(l,j,q[a[k][i][0]])&&dp(j+1,r,q[a[k][i][1]]))//按區間進行比較 return res=1;}}return res=0; } int main(){memset(f,-1,sizeof f);q['W']=0;q['I']=1;q['N']=2;q['G']=3;for(int i=0;i<4;i++)scanf("%d",&t[i]);for(int i=0;i<4;i++)for(int j=1;j<=t[i];j++)scanf("%s",a[i][j]);scanf("%s",ch+1);int n=strlen(ch+1);for(int i=0;i<4;i++)if(dp(1,n,i)){flag=1;printf("%c",s[i]);}if(!flag)printf("The name is wrong!"); }

?

轉載于:https://www.cnblogs.com/Elfish/p/7683603.html

總結

以上是生活随笔為你收集整理的bzoj1055 [HAOI2008]玩具取名 区间DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。