CF4D Mysterious Present

CF4D Mysterious Present

洛谷传送门

题目描述

Peter decided to wish happy birthday to his friend from Australia and send him a card. To make his present more mysterious, he decided to make a chain. Chain here is such a sequence of envelopes AA = { a_{1},a_{2},...,a_{n}a1,a2,...,a**n }, where the width and the height of the ii -th envelope is strictly higher than the width and the height of the (i-1)(i−1) -th envelope respectively. Chain size is the number of envelopes in the chain.

Peter wants to make the chain of the maximum size from the envelopes he has, the chain should be such, that he'll be able to put a card into it. The card fits into the chain if its width and height is lower than the width and the height of the smallest envelope in the chain respectively. It's forbidden to turn the card and the envelopes.

Peter has very many envelopes and very little time, this hard task is entrusted to you.

输入格式

The first line contains integers nn , ww , hh ( 1<=n<=50001<=n<=5000 , 1<=w,h<=10^{6}1<=w,h<=106 ) — amount of envelopes Peter has, the card width and height respectively. Then there follow nn lines, each of them contains two integer numbers w_{i}w**i and h_{i}h**i — width and height of the ii -th envelope ( 1<=w_{i},h_{i}<=10^{6}1<=w**i,h**i<=106 ).

输出格式

In the first line print the maximum chain size. In the second line print the numbers of the envelopes (separated by space), forming the required chain, starting with the number of the smallest envelope. Remember, please, that the card should fit into the smallest envelope. If the chain of maximum size is not unique, print any of the answers.

If the card does not fit into any of the envelopes, print number 00 in the single line.

题意翻译

给出一个限制 (w,h)(w,h) 和 nn 个物品的二维信息(w_i,h_i)(w**i,h**i)

求物品二维都满足 w_i>w,h_i>hw**i>w,h**i>h 的前提下的最长二维严格上升子序列以及其长度(w_i>w_{i-1},h_i > h_{i-1}(w**i>w**i−1,h**i>h**i−1 )

如果找不到任何一个物品满足条件 只需输出一行 0

---

题解：

一开始做这道题的时候没看样例，拐进了一个误区：以为位置是固定的。于是思路变成先筛选合法项，再无脑跑LIS即可，二维？不用管阿，多加一个判断就好了。（先没统计序列，只DP长度）

本地跑样例，发现第二个样例输出的是2。仔细研究一下样例，发现第二行神奇的1 3 2.发现是自己题意理解错了。

哦！位置可以随便换阿！

于是这道题变成了一个二维偏序问题。所谓二维偏序，就是给定两种限制条件，维护出一个特定关系的序列问题。其解决方法一般是：对于第一维，排序。对于第二维，DP。

可以证明，这两维的处理方法是互不影响的。也就是：第一维的排序不会影响第二维的最优特性。

那么，这道题的两种限制条件就是题目中给出的二维单调增（那个最初的限制条件可以预处理得出，不算）。所以我们先在读入的时候筛掉不合法项目，然后对所有合法项目排序（第一维搞定）。在第二维跑LIS即可。在LIS的过程中记录pre数组，表示当前元素的上一个元素是谁。这样就构成了一个链表结构，可以在最后的时候链式输出。

但是第10个点WA了。

为什么呢？

去CF上看了数据，发现没有判重。也就是说求了个非严格上升子序列。之后想着去重，一顿YY什么新开结构体，set等等不着边际的东西。后来发现，不用阿！直接在DP的过程中加一个限制条件不就好了？

于是可以AC：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5010;
int n,ww,hh,ans,pos,cnt;
int w[maxn],h[maxn],dp[maxn],pre[maxn],fsw[maxn];
//dp[i]表示以i结尾的最长二维严格上升子序列长度。
struct node
{
	int we,he,id;	
}a[maxn];
int tot;
bool cmp(node a,node b)
{  
	return a.we<b.we;
}
int main()
{
	scanf("%d%d%d",&n,&ww,&hh);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&w[i],&h[i]);
		if(w[i]>ww && h[i]>hh)
			a[++tot].we=w[i],a[tot].he=h[i],a[tot].id=i;
	}
	if(!tot)
	{
		printf("%d",tot);
		return 0;
	}
	sort(a+1,a+tot+1,cmp);
	for(int i=1;i<=tot;i++)
	{
		for(int j=0;j<i;j++)
			if(a[j].he<a[i].he && a[j].we<a[i].we)
				if(dp[i]<dp[j]+1)
				{
					dp[i]=dp[j]+1;
					pre[i]=j;
				}
		if(dp[i]>ans)
		{
			ans=dp[i];
			pos=i;
		}
	}
	printf("%d
",ans);
	while(pos)
	{
		fsw[++cnt]=a[pos].id;
		pos=pre[pos];
	}
	for(int i=cnt;i>=1;i--)
		printf("%d ",fsw[i]);
	return 0;
}