CF1446B Catching Cheaters

题意给你两个字符串我们需要从中选出两个子串求出它们的最大公共子序列后定义k4*lis(a,b)-|a|-|b|你需要求出最大的k并输出。做法看到最大公共子序列就 连接小脑并想出dp(啥玩意) 。设dp[i][j]表示a匹配到ib匹配到j的最大相似度 。for(int i1;in;i){ for(int j1;jm;j){ if(a[i]b[j]){ dp[i][j]max(dp[i][j],dp[i-1][j-1]2); } dp[i][j]max({dp[i][j],dp[i][j-1]-1,dp[i-1][j]-1}); ansmax(ans,dp[i][j]); } }咋评的cf1800。完整代码(求赞)#includebits/stdc.h using namespace std; const int N5e35; int n,m,ansINT_MIN,dp[N][N];//dp[i][j]表示a匹配到ib匹配到j的最大相似度 string a,b; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinnmab; a_a,b_b; for(int i1;in;i){ for(int j1;jm;j){ if(a[i]b[j]){ dp[i][j]max(dp[i][j],dp[i-1][j-1]2); } dp[i][j]max({dp[i][j],dp[i][j-1]-1,dp[i-1][j]-1}); ansmax(ans,dp[i][j]); } } printf(%d,ans); return ~(-1); }