Codeforces Beta Round #4 (Div. 2 Only) D. Mysterious Present（LIS）

传送门

题意：

　　现在我们有 n 个信封，然后我们有一张卡片，并且我们知道这张卡片的长和宽。

　　现给出这 n 个信封的长和宽，我们想形成一个链，这条链的长度就是这条链中所含有的信封的数量；

　　但是需要满足①信封a可以连接信封b当且仅当信封a的长和宽分别严格小于信封b的长和宽。

　　　　　　       ②构成这条长链的所有信封的长和宽分别严格小于卡片的长和宽。

　　问最多可以形成多长的链，并且输出我们选取的链的编号；

题解：

　　DAG上的动态规划；

　　如果信封对于任意两个信封 a,b 满足上述条件①②，那么连一条由a指向b的有向边；

　　O(n)预处理出所有满足条件的(a,b)；

　　求解DAG上的最长路；

　　正解，nice，可你别忘了，最大需要开 n = 25000000 的数组存图，emmm；

　　

　　然后，不断地试探，最终

　　

　　啊，最后一个点，翻车了；

　　出题人也太坏了叭；　　

　　正解：首先对于这 n 个信封，按照 w 从小到大排序，然后，找 h 的最长上升子序列；

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define memF(a,b,n) for(int i=0;i <= n;a[i]=b,++i);

 const int maxn=5e3+;

 int n,w,h;

 struct Date

 {

     int w,h;

     int id;

     bool operator < (const Date& obj) const

     {

         return w < obj.w;

     }

 }_date[maxn];

 int dp[maxn];

 bool isSat(int i,int j)

 {

     return _date[i].w < _date[j].w && _date[i].h < _date[j].h;

 }

 void Solve()

 {

     sort(_date+,_date+n+);

     memF(dp,,n);

     for(int i=n-;i >= ;--i)

         for(int j=i+;j <= n;++j)

             if(isSat(i,j))

                 dp[i]=max(dp[j]+,dp[i]);

     int ans=;

     int cur;

     for(int i=;i <= n;++i)

         if(isSat(,i) && dp[i] > ans)

         {

             ans=dp[i];

             cur=i;

         }

     printf("%d\n",ans);

     if(ans == )

         return ;

     printf("%d",_date[cur].id);

     for(int i=;i <= n;++i)

         if(dp[i] == dp[cur]- && isSat(cur,i))

             printf(" %d",_date[i].id),cur=i;

     printf("\n");

 }

 int main()

 {

     scanf("%d%d%d",&n,&w,&h);

     for(int i=;i <= n;++i)

     {

         scanf("%d%d",&_date[i].w,&_date[i].h);

         _date[i].id=i;

     }

     _date[]={w,h};

     Solve();

     return ;

 }