又是那个lis变形的题目。
但是不好定义严格的比较符号，因此只能n^2去做。值得注意的一个是要先排序，因为可能可以先选后面的再选前面的，先排序的话就能够避免这个问题。但是要注意，因为要输出路径，所以要记录之前的id。
代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
using namespace std;
const int N = + ;
const int inf = 0x3f3f3f3f; struct node
{
int a,b,id;
bool operator < (const node & temp) const
{
return a == temp.a ? b > temp.b : a < temp.a;
}
}p[N];
struct state
{
int now,pre,len;
}dp[N]; int main()
{
int n = ;
int a,b;
while(scanf("%d%d",&a,&b) == )
{
n++;
p[n] = (node){a,b,n};
//if(n == 9) break;
}
sort(p+,p++n);
for(int i=;i<=n;i++)
{
int pos = -;
for(int j=;j<i;j++)
{
if(!(p[j].a < p[i].a && p[j].b > p[i].b)) continue;
if(pos == -) pos = j;
else if(dp[j].len > dp[pos].len) pos = j;
}
if(pos == -) dp[i] = (state){i,-,};
else dp[i] = (state){i,pos,dp[pos].len + };
}
int ind = ;
for(int i=;i<=n;i++)
{
if(dp[i].len > dp[ind].len) ind = i;
}
stack<int> S;
int temp = ind;
while(ind != -)
{
S.push(ind);
ind = dp[ind].pre;
}
printf("%d\n",S.size());
while(!S.empty())
{
int x = S.top(); S.pop();
printf("%d\n",p[x].id);
}
return ;
}