Gym - 102307C Common Subsequence
题意：给你两个相同长度的DNA序列，判断这两个的最长公共子序列长度是不是0.99*n，n为序列的长度(n<=1e5)。
嗯，正常dp的想法是n2，肯定是会超时的，那么我们把目光放到0.99*n这里，反过来不就是最多只能失配0.01*n，最大也就是1000个字符。
所以接下来就是不看大佬做法，自己完全没想到的dp设法。dp[i][j]就代表s1串抛弃了i个字符，s2抛弃了j个字符的最长公共子序列长度。
那么此时，s1串已经匹配了的序列长度就是i+dp[i][j]，s2已经匹配的序列长度就是j+dp[i][j]。
然后当s1的第i+dp[i][j]+1个字符跟s2的第j+dp[i][j]+1个字符匹配时，如果匹配成功，明显dp[i][j]++
而如果此时失配了，那么就是s1串抛弃第i+dp[i][j]+1个字符或者s2抛弃第j+dp[i][j]+1个字符，那么此时就是用dp[i][j]来更新它们。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1e3+11,M=1e5+11; 6 char s1[M],s2[M]; 7 int dp[N][N]; 8 int main(){ 9 int n,m,ans; 10 while(~scanf("%s%s",s1+1,s2+1)){ 11 ans=0; 12 n=strlen(s1+1); 13 m=n/100+n%100; 14 for(int i=0;i<=m;i++) 15 for(int j=0;j<=m;j++) dp[i][j]=0; 16 for(int i=0;i<=m;i++){ 17 for(int j=0;j<=m;j++){ 18 while(i+dp[i][j]+1<=n&&i+dp[i][j]+1<=n){ 19 if(s1[i+dp[i][j]+1]==s2[j+dp[i][j]+1]) dp[i][j]++; 20 else break; 21 } 22 dp[i+1][j]=max(dp[i+1][j],dp[i][j]); 23 dp[i][j+1]=max(dp[i][j+1],dp[i][j]); 24 ans=max(ans,dp[i][j]); 25 } 26 } 27 if(ans*100>=99*n) printf("Long lost brothers D:\n"); 28 else printf("Not brothers :(\n"); 29 } 30 return 0; 31 }
Gym - 102307C Common Subsequence 搞不懂的dp
原文：https://www.cnblogs.com/LMCC1108/p/11672734.html
