继续大战dp。2018年11月30日修订，更新一下现在看到这个题目的理解（ps：就现在，poj又503了）。

题意分析

这条题目的大意是这样的，问一字符串内最少删去多少的字符使其由给定的若干字符串构成。非常好的一道字符串dp题。
具体的dp解法是什么呢？考虑一下我们删去的这个过程。比如说这个式子

throw

thraow

我们要不然删去a，要不然删去 “thraow”才能满足由第一个式子构成的这个条件（空串也算被第一个式子构造了）。但是，程序如何知道删去a是使这俩个单词匹配的最优决策？

我们这样考虑：每次从后往前考虑到第i个字符的时候，我有两个决策：一，这个字符不行，删掉（这是个始终合理的答案）。二，这个字符很行，从它($str_i$)到某个字符（$str_j$）结束，是能够在删除若干字符的情况下匹配到某个目标串的（也就是说，某个目标串是$(i,j)$的子序列），那么从这个串到末尾的不能匹配的情况就变成（或者说“转移”）从那个目标串结束之后的字符开始的情况了（当然需要更新一下我删去的字符的数目）。

因此，有了上面这些思维过程，就可以想到设立$dp[i]$保存每次删去的最小值，并且从右往左去处理。这样，$dp[i]$的意思就是“从i->end删除最少的值”。
而转移方程自然很容易得出了：$$dp[i]={dp[i+1]+1,dp[cur]+L-cur-i}$$，第二个仅当目标字符串能够在[i,cur]中间删去若干字符后完成匹配可用。

代码

#include <cstring>

#include <algorithm>

#include <iostream>

#include <queue>

#include <set>

#include <map>

#include <vector>

using namespace std;

typedef unsigned long long ull;

int dp[305];

int main()

{

    int w,l;

    while(cin>>w>>l)

    {

        string wstr; cin>>wstr;

        vector<string> lstr;

        for(int i=1;i<=w;++i)

        {

            string tmp; cin>>tmp;

            lstr.push_back(tmp);

        }

        dp[l]=0;

        for(int i=l-1;i>=0;--i)

        {

            dp[i]=dp[i+1]+1;

            //printf("dp[%d]=%d.\n",i,dp[i+1]+1);

            for(int j=0;j!=w;++j)

            {

                int len=lstr[j].length();

                if(len<=l-i && lstr[j][0]==wstr[i])

                {

                    int curw=i,curl=0;

                    while(curw<l)

                    {

                        if(lstr[j][curl]==wstr[curw++])

                            curl++;

                        if(curl==len)

                        {

                            dp[i]=min(dp[i],dp[curw]+curw-i-len);

                            //printf("[Changed]dp[%d]=%d.\n",i,dp[i]);

                            break;

                        }

                    }

                }

            }

        }

        cout<<dp[0]<<endl;

    }

    return 0;

}

巴特西

【个人训练】The Cow Lexicon（POJ-3267）

题意分析

代码

最新文章

热门文章