Portal

Title:

Now we have n envelopes, then we have a card, and we know the length and width of the card.

Now we give the length and width of these n envelopes. We want to form a chain. The length of this chain is the number of envelopes contained in this chain;

But it needs to meet the following requirements: (1) envelope a can connect envelope b if and only if the length and width of envelope a are strictly smaller than the length and width of envelope b respectively.

② the length and width of all envelopes forming this long chain are strictly smaller than that of the card.

Ask how long the chain can be formed at most, and output the chain number we selected;

Explanation:

Dynamic planning on DAG;

If the envelope for any two envelopes a and b meet the above conditions ① ②, then connect a directed edge from a to b;

O (N 2) pretreates all (a,b) that meet the conditions;

Solving the longest path on DAG;

Positive solution, nice, but don't forget, the maximum need is to open the array memory of n2 = 25000000, emmm;

And then, constantly testing, eventually

Ah, at the last point, the car overturned;

The writer is too bad

Positive solution: first of all, for these n envelopes, we rank w from small to large, and then find the longest ascending subsequence of h;

AC Code:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define memF(a,b,n) for(int i=0;i <= n;a[i]=b,++i);
 4 const int maxn=5e3+50;
 5 
 6 int n,w,h;
 7 struct Date
 8 {
 9     int w,h;
10     int id;
11     bool operator < (const Date& obj) const
12     {
13         return w < obj.w;
14     }
15 }_date[maxn];
16 int dp[maxn];
17 
18 bool isSat(int i,int j)
19 {
20     return _date[i].w < _date[j].w && _date[i].h < _date[j].h;
21 }
22 void Solve()
23 {
24     sort(_date+1,_date+n+1);
25     memF(dp,1,n);
26     for(int i=n-1;i >= 1;--i)
27         for(int j=i+1;j <= n;++j)
28             if(isSat(i,j))
29                 dp[i]=max(dp[j]+1,dp[i]);
30 
31     int ans=0;
32     int cur;
33     for(int i=1;i <= n;++i)
34         if(isSat(0,i) && dp[i] > ans)
35         {
36             ans=dp[i];
37             cur=i;
38         }
39 
40     printf("%d\n",ans);
41     if(ans == 0)
42         return ;
43     
44     printf("%d",_date[cur].id);
45     for(int i=1;i <= n;++i)
46         if(dp[i] == dp[cur]-1 && isSat(cur,i))
47             printf(" %d",_date[i].id),cur=i;
48     printf("\n");
49 }
50 int main()
51 {
52     scanf("%d%d%d",&n,&w,&h);
53     for(int i=1;i <= n;++i)
54     {
55         scanf("%d%d",&_date[i].w,&_date[i].h);
56         _date[i].id=i;
57     }
58     _date[0]={w,h};
59 
60     Solve();
61 
62     return 0;
63 }