【题解】Is Bigger Smarter?

题目链接: Is Bigger Smarter?

题意:

给定一系列大象的体重和IQ, 对于所有大象求一个序列, 要求序列中大象的体重严格上升, IQ严格下降.

思路:

最长上升子序列变形, 比较基础的动态规划. 容易想到可以先对体重或者IQ排序, 如果是前者就求IQ的最长下降子序列, 如果是后者就求体重的最长上升子序列.

一个容易忽略的点是sort对pair排序时优先对first上升排序, 如果相同就对second上升排序, 而这里因为如果对体重上升排序, 那么就要求对IQ下降排序, 所以如果直接用sort对pair排序必wrong.

错误代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<string>
#include<cstring>
#include<set>
#include<map>

using namespace std;

const int N = 10010;
#define ll long long

pair<int, pair<int, int>>p[N];
int g[N],f[N],a[N];
int n;

int main()
{
	int n = 0,x,y;
	while (cin >> x && cin >> y)
	{
		p[++n].first = x;
		p[n].second.first = y;
		p[n].second.second = n;
	}

	sort(p + 1, p + n + 1);//对体重上升排序
	//for (int i = 1; i <= n; ++i)cout << p[i].first <<" "<<p[i].second.first<<" "<<p[i].second.second << endl;

	for (int i = 1; i <= n; ++i)f[i] = 1;

	for (int i = 1; i <= n ; ++i)//求IQ的最长下降子序列
	{
		for (int j = 1; j < i; ++j)
		{
			if (p[i].second.first < p[j].second.first)
				if (f[i] < f[j] + 1)
				{
					f[i] = f[j] + 1;
					g[i] = j;
				}
		}
	}

	int res = 1;
	for (int i = 1; i <= n; ++i)if (f[i] > f[res])res = i;
	cout << f[res] << endl;
	n = f[res];
	for (int i = 1; i <= n; ++i)
	{
		a[i]=p[res].second.second;
		res = g[res];
	}

	for (int i = n; i >=1; --i)cout << a[i] << endl;//逆序输出路径

	return 0;
}

AC代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<string>
#include<cstring>
#include<set>
#include<map>

using namespace std;

const int N = 10010;
#define ll long long
#define PII pair<int,int>

pair<pair<int, int>,int>p[N];
int g[N],f[N],a[N];
int n;

bool cmp(pair<pair<int, int>, int>a, pair<pair<int, int>, int>b)
{
	if (a.first.second == b.first.second)
		return a.first.first < b.first.first;
	return a.first.second > b.first.second;
}

int main()
{
	int n = 0,x,y;
	while (cin >> x && cin >> y)
	{
		p[++n].first.first = x;
		p[n].first.second = y;
		p[n].second = n;
	}

	sort(p + 1, p + n + 1,cmp);
	//for (int i = 1; i <= n; ++i)cout << p[i].first.first << " " << p[i].first.second << " " << p[i].second << endl;
	
	for (int i = 1; i <= n; ++i) f[i] = 1;
	
	for (int i = 1; i <= n; ++i)
	{
		for(int j=1;j < i;++j)
			if (p[i].first.first > p[j].first.first)
				if (f[i] < f[j]+1)
				{
					f[i] = f[j] + 1;
					g[i] = j;
				}
	}
	
	int res = 1;
	for (int i = 1; i <= n; ++i)
		if (f[res] < f[i])
			res = i;
	cout << f[res] << endl;
	
	n = f[res];
	for (int i = 1; i <= n; ++i)
	{
		a[i] = p[res].second;
		res = g[res];
	}
	for (int i = n; i >= 1; --i)cout << a[i] << endl;
	
	return 0;

}