又是那个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 ;
}

最新文章

  1. Atitit 图像处理的心得与疑惑 attilax总结
  2. SOUI与WTL
  3. HTTP和HTTPS
  4. 【转】Gvim开发环境配置笔记--Windows篇
  5. 浅议iOS网络数据解析
  6. SharePoint Server 2007 简体中文下载
  7. ubuntu 12.04 搭建nginx + php + mysql +phpmyadmin
  8. WINHTTP的API接口说明
  9. .Net 中的反射机制
  10. idea编译时JDK版本变化
  11. SQL Server 查询性能优化——创建索引原则(一)(转载)
  12. 开启ucosii的移植之旅
  13. WinServer-FTP搭建
  14. Bootstrap模态框修改出现的位置和大小
  15. 通俗bandit算法
  16. VMware 虚拟机安装OSX el capitan 11.12
  17. crontab入门及进阶学习笔记
  18. Win7 64bit 安装VisualSVN出现报错:Servic &amp;#39;VisualSVN Server&amp;#39; failed to start.解决的方法
  19. 【WinForm程序】注册热键快捷键切换
  20. python3.5过滤网址和图片的函数自己亲测可用

热门文章

  1. node 和 postgres
  2. 常用shell命令积累
  3. mysql8中查询语句表别名不能使用 “of”
  4. 记一次Git提交报错的问题
  5. Express无法解析POST请求的JSON参数
  6. 关于将多个json对象添加到数组中的测试
  7. c#排序sql语句查询
  8. JS实现数组去重(重复元素保留一个)
  9. springboot和Redis集群版的整合
  10. Oracle 11g Dataguard 配置,维护与详解 (ADG)