问题遇到的现象和发生背景
https://atcoder.jp/contests/dp/tasks/dp_f
问题相关代码,请勿粘贴截图
#include<bits/stdc++.h>
using namespace std;
const int M = 5000;
std::string ssz[M][M];
std::string a;
std::string b;
int dp[M][M];
int main()
{
getline(cin,a);
getline(cin,b);
string j = " ";
a=j+a;
b=j+b;
for(int i = 1;i <= a.size(); i++)
for(int j = 1; j <= b.size(); j++){
if(a[i] == b[j]) {dp[i][j]=dp[i-1][j-1]+1;ssz[i][j]=b[j];}
else {
if(dp[i-1][j]>dp[i][j-1]) {
dp[i][j]=dp[i-1][j];
ssz[i][j]=ssz[i-1][j];
}
else {
dp[i][j]=dp[i][j-1];
ssz[i][j]=ssz[i][j-1];
}
}
}
stack<string>s;
int n,m;
n=a.size(); m=b.size();
while(dp[n][m]) {
if(dp[n-1][m-1] +1 ==dp[n][m]) {s.push(ssz[n][m]);
n--;m--;
}
else {
if(dp[n-1][m]>=dp[n][m-1]) {
n--;
}
else {
m--;
}
}
}
while(!s.empty()){
cout<<s.top();
s.pop();
}
}