大體題意：

給你兩個字符串，求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**/