//
// main.cpp
// Richard
//
// Created by 邵金杰 on 16/9/15.
// Copyright © 2016年 邵金杰. All rights reserved.
//
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
int dp[maxn],f[maxn];
struct node{
int w,s,index;
}p[maxn];
int cmp(node &a,node &b){
if(a.w!=b.w) return a.w<b.w;
return a.s>b.s;
}
int main()
{
int k=1;
while(scanf("%d%d",&p[k].w,&p[k].s)!=EOF) {dp[k]=1;p[k].index=k;k++;}
sort(p+1,p+k,cmp);
int len=0,pos=-1;
memset(f,-1,sizeof(f));
for(int i=1;i<k;i++)
{
for(int j=1;j<i;j++)
{
if(p[i].w>p[j].w&&p[i].s<p[j].s&&dp[j]+1>dp[i]){//dp[j]+1>dp[i]一定要判断,否则f会指错
dp[i]=max(dp[i],dp[j]+1);
f[i]=j;
if(dp[i]>len){
len=dp[i];pos=i;
}
}
}
}
int s[maxn];
int x=0;
if(len==0) printf("1\n1\n");
else printf("%d\n",len);
while(pos!=-1)
{
s[x++]=p[pos].index;
pos=f[pos];
}
for(int i=x-1;i>=0;i--) printf("%d\n",s[i]);
}
转载请注明原文地址: https://ju.6miu.com/read-1132107.html