HDU3109： Worms（字符串变换类 DP）

pro：开始有一个字母虫，然后字母虫在每一天可以选择自己身上的部分字母变换，变换规则形如A->BC。现状给定最终字母虫的字符串，求最少用了多少天。

如有规则A->BC，B->AC，C->AB；则ACAB可以见过三天(A-BC-ACC-ACAC)或者两天(A-BC-ACAB)得来。规则不超过80，字符串长度不超过50；

sol：dp[i][j][p]表示，最开始只有字母p，变换到[i,j]区间的最小天数。

显然初始：dp[i][i][x]=c[i]==x?0:inf;

其他： dp[i][j][x]=min(dp[i][k][p],dp[k+1][j][q]+1); 当且当存在规则x->pq；

经验：在倒推比较难的情况下，我们表示的状态可以是最初状态。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

char c[maxn],s[maxn*][];

int dp[maxn][maxn][maxn];

vector<int>A[],B[];

int main()

{

    int N,L;

    while(~scanf("%d",&N)){

        if(!N) break;

        rep(i,,) A[i].clear(),B[i].clear();

        rep(i,,N){

             scanf("%s",s[i]);

             A[s[i][]-'A'].push_back(s[i][]-'A');

             B[s[i][]-'A'].push_back(s[i][]-'A');

        }

        scanf("%s",c+); L=strlen(c+);

        rep(i,,L) rep(j,i,L) rep(k,,) dp[i][j][k]=L+;

        rep(i,,L) dp[i][i][c[i]-'A']=;

        rep(i,,L) {

            rep(l,,L-i){

                int r=l+i;

                rep(p,,){

                    rep(k,l,r-){

                        for(int t=;t<A[p].size();t++){

                            dp[l][r][p]=min(dp[l][r][p],max(dp[l][k][A[p][t]],dp[k+][r][B[p][t]])+);

                        }

                    }

                }

            }

        }

        int ans=L+;

        rep(i,,) if(dp[][L][i]!=-) ans=min(ans,dp[][L][i]);

        if(ans==L+) ans=-;

        printf("%d\n",ans);

    }

    return ;

}

巴特西

HDU3109： Worms（字符串变换类 DP）

最新文章

热门文章