题目:AT_dp_f LCS

Runtime Error

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int al,bl;
struct node{
	int sum;
	string ans;
}dp[3005][3005];
string a,b;
int main(){
	cin>>a>>b;
	al=a.size();
	bl=b.size();
	a=' '+a;
	b=' '+b;
	dp[1][1].sum=0;
	for(int i=1;i<=al;i++)
		for(int j=1;j<=bl;j++)
			if(a[i]==b[j]) dp[i][j].sum=dp[i-1][j-1].sum+1,dp[i][j].ans=dp[i-1][j-1].ans+a[i];
			else if(dp[i][j-1].sum>dp[i-1][j].sum) dp[i][j].sum=dp[i][j-1].sum,dp[i][j].ans=dp[i][j-1].ans;
			else dp[i][j].sum=dp[i-1][j].sum,dp[i][j].ans=dp[i-1][j].ans;
	cout<<dp[al][bl].ans;
	return 0;
}
/*
*/

当输入为两个一模一样的长度为3000的字符串时，电脑卡死了。

推测是 string 太多导致的，求调。