求助,Wa on #1_05,#1_09
  • 板块AT_dp_f LCS
  • 楼主guozhetao
  • 当前回复0
  • 已保存回复1
  • 发布时间2024/10/3 16:49
  • 上次更新2024/10/3 19:34:47
查看原帖
求助,Wa on #1_05,#1_09
669924
guozhetao楼主2024/10/3 16:49

求 hack 数据或指出错误

#include<bits/stdc++.h>
#define int long long
using namespace std;
string a,b;
int n,m;
string dp[2][30505];
signed main() {
	cin >> a >> b;
	n = a.size(),m = b.size(); 
	for(int j = 0;j < m;j++) {
		if(a[0] == b[j]) dp[0][j] = a[0];
		else if(j != 0)dp[0][j] = dp[0][j - 1];
	}
	for(int i = 1;i < n;i++) {
		//printf("\n%lld:",i);
		if(a[i] == b[0]) dp[i & 1][0] = a[0];
		else dp[i & 1][0] = dp[(i + 1) & 1][0];
		for(int j = 1;j < m;j++) {
			if(a[i] == b[j]) dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + a[i];
			else if(dp[(i + 1) & 1][j].size() >= dp[i & 1][j - 1].size())dp[i & 1][j] = dp[(i + 1) & 1][j];
			else dp[i & 1][j] = dp[i & 1][j - 1];
			//printf("%lld ",j);
		}
	}
	cout<<dp[(n - 1) & 1][m - 1];
}

2024/10/3 16:49
加载中...