D - Mysterious Present

柔光的暖阳◎ 2021-12-11 12:29 243阅读 0赞

这个题和求最长递增序列的题类似，为了能输出一组可行的数据，我还用了一点儿链表的知识。

Description

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 *A* = \{ *a*1,  *a*2,  ...,  *a**n*\}, where the width and the height of the *i*\-th envelope is strictly higher than the width and the height of the (*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.

Input

The first line contains integers *n*, *w*, *h* (1  ≤ *n* ≤ 5000, 1 ≤ *w*,  *h*  ≤ 106) — amount of envelopes Peter has, the card width and height respectively. Then there follow *n* lines, each of them contains two integer numbers *w**i* and *h**i* — width and height of the *i*\-th envelope (1 ≤ *w**i*,  *h**i* ≤ 106).

Output

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 0 in the single line.

Sample Input

Input

2 1 1  2 2  2 2

Output

1  1

Input

3 3 3  5 4  12 11  9 8

Output

3  1 3 2

#include<iostream>
    using namespace std;
    struct envelope
    {
    	int num,w,h;
    	bool valid;
    	envelope*last;
    };
    int main()
    {
    	int n,w,h,i,j;
    	cin>>n>>w>>h;
    	envelope *env=new envelope[n];
    	int *seq=new int[n];
    	for(i=0;i<n;i++)
    		seq[i]=1;
    	for(i=0;i<n;i++)
    	{
    		cin>>env[i].w>>env[i].h;
    		env[i].num=i+1;
    		env[i].valid=true;                //表示信封是否可用
    		env[i].last=NULL;                 //能装入的上一个信封
    	}
    	for(i=0;i<n-1;i++)                    //先对信封进行排序；
    	{
    		int k=i;
    		for(j=i+1;j<n;j++)
    		{
    			if(env[k].w>env[j].w||env[k].w==env[k].w&&env[k].h>env[k].h)
    				k=j;
    		}
    		swap(env[k],env[i]);
    	}
    	for(i=0;i<n;i++)                       //判断信封是否可用
    	{
    		if(!(env[i].w>w&&env[i].h>h))
    		{
    			env[i].valid=false;                     
    			seq[i]=0;
    		}
    	}
    	for(i=0;i<n;i++)                       //找出第一个可用的信封
    		if(env[i].valid==true)
    			break;
    	int t=i;	
    	for(i=t+1;i<n;i++)
    	{
    		if(seq[i]==0)                      //如果信封不可用，跳过。开始这个没写，老是在第16组数据WA
    			continue;                                             
    		for(j=t;j<i;j++)
    			if(env[i].w>env[j].w&&env[i].h>env[j].h)
    			{
    				int tem=seq[j]+1;
    				if(tem>seq[i])
    				{
    					seq[i]=tem;
    					env[i].last=&env[j];   //记录上一个信封的地址
    				}
    			}
    	}
    	int max=0,index=0;
    	for(i=0;i<n;i++)                       //找出能嵌套的最多的信封个数及其 中一个最大的信封的下标
        {		                                                     
    		if(seq[i]>max)
    		{
    			max=seq[i];
    			index=i;
    		}
    	}
    	cout<<max<<endl;
    	if(max==0)                                                    
    		return 0;
    	else                                   //寻找内层的信封，并将其序号记录在ans数组中
    	{                                                                  
    		int *ans=new int[n];
    		envelope *p=&env[index];
    		for(i=max;i>0;i--)
    		{
    			ans[i]=p->num;
    			p=p->last;		
    		}
    		for(i=1;i<=max;i++)
    		{
    			cout<<ans[i];
    			if(i!=max)
    				cout<<' ';
    		}
    		cout<<endl;
    	}
    }

转载于:https://www.cnblogs.com/aljxy/p/3234249.html