ICPCCamp2017 Day 4 B Dissertation（LCS 动态规划--改进版 ）

大体题意：

给你两个字符串，求LCS的长度，一个不超过100W，一个不超过1000

思路：

正常的LCS的dp肯定不能进行，这样会超时。

令dp[i][j]表示当前枚举的LCS的长度为第i位，字符为第二个字符串的的第j 个字符。dp[i][j] 为第一个字符串的的前哪个位置。

那么假设dp[i][j] 是已知的话，那么考虑转移第j+1个字符，假设对LCS没有贡献的话，只能转移 dp[i][j+1] = min(dp[i][j]);

否则有贡献的话，既能转移 DP[i][j+1] 也能转移 dp[i+1][j+1]

不要漏掉状态，否则会WA掉。

#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#define Siz(x) (int)x.size()#define Max(a,b) ((a)>(b)?(a):(b))using namespace std;const int inf = 0x3f3f3f3f;char s1[1000000+7];char s2[1007];int T;int dp[1007][1007];vector<int>g[2][26];vector<int>::iterator it;char t[1000000+7];int main(){    scanf("%d",&T);    while(T--){        scanf("%s%s",s1+1,s2+1);        int len1 = strlen(s1+1);        int len2 = strlen(s2+1);        if (len1 < len2){            swap(len1,len2);            strcpy(t+1,s1+1);            strcpy(s1+1,s2+1);            strcpy(s2+1,t+1);        }        for (int i = 0; i < 2; ++i){            for (int j = 0; j < 26; ++j) g[i][j].clear();        }        for (int i = 1; i <= len1; ++i){            int id=s1[i]-'a';            g[0][id].push_back(i);        }        memset(dp,inf,sizeof dp);        for (int i = 1; i <= len2; ++i){            int id=s2[i]-'a';            g[1][id].push_back(i);        }        bool ok = 0;        for (int j = 1; j <= len2; ++j){            int id = s2[j]-'a';            if (Siz(g[0][id]))dp[1][j] = g[0][id].front(),ok = 1;        }        int ans = ok;//        PRintf("%d/n",ans);        for (int i = 1; i < 1007; ++i){            for (int j = 1; j < len2; ++j){                if (dp[i][j] != inf){                    int id = s2[j+1] - 'a';                    if (Siz(g[0][id]))it = lower_bound(g[0][id].begin(),g[0][id].end(),dp[i][j]+1);//                    printf("%c %d %d %d/n",id+'a',dp[i][j]+1,i,j);                    if (!Siz(g[0][id]) || it == g[0][id].end() ){                        dp[i][j+1] = min(dp[i][j],dp[i][j+1]);                        ans = Max(ans,i);                    }                    else {//                        printf("haha/n");                        dp[i+1][j+1] = min(*it,dp[i+1][j+1]);                        dp[i][j+1] = min(dp[i][j+1],dp[i][j]); /// 状态转移不要漏掉。。                        ans = Max(ans,i+1);                    }                }            }        }        printf("%d/n",ans);    }    return 0;}/**111abcdefghijklmnopqrstuvwxyzbbddeemmmiimmm3ijhhjaij2**/