又是那个lis变形的题目。

　　但是不好定义严格的比较符号，因此只能n^2去做。值得注意的一个是要先排序，因为可能可以先选后面的再选前面的，先排序的话就能够避免这个问题。但是要注意，因为要输出路径，所以要记录之前的id。

　　代码如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int N = 1000 + 5; 7 const int inf = 0x3f3f3f3f; 8  9 struct node10 {11     int a,b,id;12     bool operator < (const node & temp) const13     {14         return a == temp.a ? b > temp.b : a < temp.a;15     }16 }p[N];17 struct state18 {19     int now,pre,len;20 }dp[N];21 22 int main()23 {24     int n = 0;25     int a,b;26     while(scanf("%d%d",&a,&b) == 2)27     {28         n++;29         p[n] = (node){a,b,n};30         //if(n == 9) break;31     }32     sort(p+1,p+1+n);33     for(int i=1;i<=n;i++)34     {35         int pos = -1;36         for(int j=1;j
         
           p[i].b)) continue;39             if(pos == -1) pos = j;40             else if(dp[j].len > dp[pos].len) pos = j;41         }42         if(pos == -1) dp[i] = (state){i,-1,1};43         else dp[i] = (state){i,pos,dp[pos].len + 1};44     }45     int ind = 1;46     for(int i=2;i<=n;i++)47     {48         if(dp[i].len > dp[ind].len) ind = i;49     }50     stack
          
            S;51 int temp = ind;52 while(ind != -1)53 {54 S.push(ind);55 ind = dp[ind].pre;56 }57 printf("%d\n",S.size());58 while(!S.empty())59 {60 int x = S.top(); S.pop();61 printf("%d\n",p[x].id);62 }63 return 0;64 }