这份代码第 #7 WA

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,maxn,f[1000005],a[2005],b[2005],c[2005],d[2005];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
	for(int i=1;i<=m;i++)scanf("%d%d",&c[i],&d[i]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(c[j]<a[i])continue;
			ans=max(ans,c[j]-a[i]+1);
			f[c[j]-a[i]]=max(f[c[j]-a[i]],d[j]-b[i]+1);
		} 
	}
	for(int i=ans-1;i>=0;i--)maxn=max(maxn,f[i]),ans=min(ans,i+maxn); 
	printf("%d",ans);
	return 0;
}

这份代码 AC

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,maxn,f[1000005],a[2005],b[2005],c[2005],d[2005];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
	for(int i=1;i<=m;i++)scanf("%d%d",&c[i],&d[i]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(d[j]<b[i])continue;
			ans=max(ans,d[j]-b[i]+1);
			f[d[j]-b[i]]=max(f[d[j]-b[i]],c[j]-a[i]+1);
		} 
	}
	for(int i=ans-1;i>=0;i--)maxn=max(maxn,f[i]),ans=min(ans,i+maxn); 
	printf("%d",ans);
	return 0;
}

不理解，一个是基于横向 dp，另一个基于纵向，理论上一样吧