陈奥楚蔑洛夫 @ 2021-09-14 21:29:44
#include<bits/stdc++.h>
using namespace std;
int n;
int f[10009][10009]={0};
char s[10009],t[10009];
void dp(){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(s[i]==t[j]){
f[i+1][j+1]=f[i][j]+1;
}
else{
f[i+1][j+1]=max(f[i+1][j],f[i][j+1]);
}
}
}
cout<<f[n+1][n+1]<<endl;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>s[i];
}
for(int j=1;j<=n;++j){
cin>>t[j];
}
dp();
return 0;
}
by Carnival @ 2021-09-14 21:37:36
为啥要用 char?
by Sin_qwq @ 2021-09-15 19:01:18
要用个优化,这题n^2过不了
by 陈奥楚蔑洛夫 @ 2021-09-15 19:45:44
@Gamemode 我试了一下,char改成int 然鹅和不改之前一毛一样 都是只A一个点