dp--C - Mysterious Present

C - Mysterious Present

 #include<bits/stdc++.h>

 using namespace std;

 int n, w, h;

 int maxn;//信封数

 int p;//最小信封的下标

 int listp[];

 int dp[];

 struct env{

     int w, h, num;

 }node[];

 bool comp(env a,env b){

     if(a.w != b.w)

         return a.w > b.w;

     return a.h > b.h;//信封从大到小排序

 }

 int main(){

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

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

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

         node[i].num = i+;//记录信封原下标

     }

     sort(node, node+n, comp);//信封按宽从小到大排序

     for(int i=; i<n; i++){//初始化

         dp[i] = ;

         listp[i] = -;

     }

     maxn = ;

     p = -;

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

         if(node[i].w>w && node[i].h>h ){//i可以放信

             dp[i] = ;

             if(p==-){

                 p = i;

                 maxn = ;

             }

         }

         if(dp[i] > ) {//i可以放信

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

                 if(node[j].w>node[i].w && node[j].h>node[i].h)//j可以放i

                     if(dp[i] < dp[j] + ){

                         dp[i] = dp[j] + ;

                         listp[i] = j;//i放进j

                         if(dp[i] > maxn){

                             maxn = dp[i];

                             p = i;

                         }

                     }

             }

         }

     }

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

     for(int i=p; maxn;){

         if(i==-)    break;

         printf("%d ",node[i].num);

         i = listp[i];

     }

 }

　　代码不需要太多的注释，结构体node用来存放每个信封的宽和高以及它的初始位置（后用到排序，但又需要输出是第几个信封，便在结构体内标记），这里注意di一下写的comp函数，用来作为结构体排序的标准。此题难道我的是这个最长子序列到底如何记录，我最初的想法，就是再用一个数组list，list[i] = j，用来表示第node[i].num个信封可以放到第node[j].num个信封里，但由于我一开始定义的是从小到大的函数，所以信封也是从小指到大的；而在这类dp题中，我只能在最后找到那个最长子序列的时候，记录下最大信封的下标，而这个从大返回指小的过程，真的把我难倒了，我有尝试再用一个数组反向指，都失败了。但其实我后来的改进很简单，只要将这些信封，从大到小排序，从最大的，一直排到最小的，并且是能放入卡片的序列最长的信封，再配合一开始想到的list的信封值向信封的方法，最后可实现从小信封，输出到大信封