为什么连样例都过不了?

P1439 【模板】最长公共子序列

陈奥楚蔑洛夫 @ 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一个点


|