求助最长下降子序列
查看原帖
求助最长下降子序列
537046
大眼仔Happy楼主2023/11/15 16:03
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int inline read()
{
	int num=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar();}
	return num*f;
}
int T,n,ans,f[N];
struct data{int x,y;}d[N];
//bool cmp(data A,data B){return A.x<B.x;}//WA
//bool cmp(data A,data B){return A.x!=B.x?A.x<B.x:A.y>B.y;}//WA
bool cmp(data A,data B){return A.x!=B.x?A.x<B.x:A.y<B.y;}//AC
void solve()
{
	n=read();ans=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d-%d",&d[i].x,&d[i].y);
		if(d[i].x>d[i].y)swap(d[i].x,d[i].y);
	}
	sort(d+1,d+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		f[i]=1;
		for(int j=1;j<i;j++)
			if(d[j].y>d[i].y)f[i]=max(f[i],f[j]+1);
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
}
int main(){
	T=read();while(T--)solve();
	return 0;
}

代码是对于第二个值进行求最长下降子序列,问题在自定义排序那里,为什么第三个就可以 AC,不应该是第二个吗???

2023/11/15 16:03
加载中...