感觉时间复杂度不大啊,帮蒟蒻看看呗
查看原帖
感觉时间复杂度不大啊,帮蒟蒻看看呗
841671
Szt2022楼主2024/8/5 10:22
#include<iostream>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1000001;
typedef long long ll;
int a1[maxn],a2[maxn],ans=inf;
int n;
inline int read(){
	int ans = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9'){
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return ans;
}
void write(int n1,int n2,int cnt)
{
	if(n1>=n&&n2>=n)
	ans=min(ans,cnt);
	if(cnt>=ans)
	return;
	if(a1[n1]!=a2[n2])
	write(n1+1,n2+1,cnt+1);
	else{
		write(n1+1,n2,cnt+1);
		write(n1,n2+1,cnt+1);
	}
}

int main()
{
	memset(a1,0,sizeof(a1));
	memset(a2,0,sizeof(a2));
	n=read();
	for(int i=1;i<=n;i++)
	a1[i]=read();
	for(int i=1;i<=n;i++)
	a2[i]=read();
	write(1,1,1);
	cout<<ans;
}
2024/8/5 10:22
加载中...