社区讨论

求助!91分dp代码

P1233[ICPC 2001 Taejon R] 木棍加工参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo17jeaf
此快照首次捕获于
2023/10/22 16:29
2 年前
此快照最后确认于
2023/11/02 16:08
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#include<vector>
using namespace std;

struct sb
{
	int x;
	int y;
}b[100000];
bool cmp(sb a,sb b)
{
	if(a.x==b.x) a.y>b.y;
	else return a.x>b.x;
}
long long n,a[1000000],d[1000000],len=1;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>b[i].x>>b[i].y;
	}
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
	{	
		a[i]=b[i].y;
	}
	d[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		int pos=lower_bound(d+1,d+len+1,a[i])-d;
		d[pos]=a[i];
		if(pos==len+1)len++;
	}
	cout<<len;
/*	for(int i=1;i<=n;i++)
	{
		cout<<b[i].x<<" "<<b[i].y<<endl;
	}*/
	return 0;
}

八号点错误,也找不到原因,求帮助

回复

2 条回复,欢迎继续交流。

正在加载回复...