求助 #4 RE
查看原帖
求助 #4 RE
545601
Mr_Biantainne楼主2024/1/11 20:03
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll nowp, n, w, h, ww, hh, f[5005], pt[5005], ans, idex = -1;
struct obj
{
	ll w, h, pos;
}a[5005];
bool cmp(obj ta, obj tb)
{
	if (ta.w == tb.w) return ta.h > tb.h;
	return ta.w < tb.w;
}
vector <ll> v;
int main()
{ 
	cin >> n >> w >> h; 
	while (n--)
	{
		cin >> ww >> hh;
		if (ww <= w || hh <= h) continue;
		a[++nowp].w = ww;
		a[nowp].h = hh;
		a[nowp].pos = nowp;
		pt[nowp] = -1;
	} 
	sort(a + 1, a + nowp + 1, cmp);
	for (ll i = 1; i <= nowp; i++)
	{
		f[i] = 1;
		for (ll j = 1; j < i; j++)
		{
			if (a[j].h < a[i].h && f[j] + 1 > f[i])
			{
				f[i] = f[j] + 1;
				pt[i] = j;
			}
		}
		if (f[i] > ans)
		{
			ans = f[i];
			idex = i;
		} 
	}
	while (idex != -1)
	{
		v.push_back(a[idex].pos);
		idex = pt[idex];
	}
	cout << v.size() << endl;
	for (ll i = v.size() - 1; i >= 0; i--) cout << v[i] << " ";
}
2024/1/11 20:03
加载中...