题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1160

给你一些老鼠的体重和速度,问你最多需要几只可以证明体重越重速度越慢,并输出任意一组答案。

结构体按照体重从小到大排序,然后根据速度就是最长下降子序列。

 //#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = ;
struct Mouse {
int fat, run, id;
bool operator <(const Mouse& cmp) const {
if(fat == cmp.fat)
return run > cmp.run;
return fat < cmp.fat;
}
}a[N];
int dp[N];
int pre[N], ans[N]; int main()
{
int f = ;
while(scanf("%d %d", &a[f].fat, &a[f].run) != EOF) {
a[f].id = f;
f++;
}
for(int i = ; i <= f; ++i) {
pre[i] = i;
}
sort(a + , a + f);
memset(dp, , sizeof(dp));
int Max = , pos = ;
for(int i = ; i < f; ++i) {
dp[i] = ;
for(int j = ; j < i; ++j) {
if(a[i].fat > a[j].fat && a[i].run < a[j].run) {
if(dp[j] + > dp[i]) {
pre[a[i].id] = a[j].id;
dp[i] = dp[j] + ;
}
}
}
if(dp[i] > Max) {
pos = a[i].id;
Max = dp[i];
}
}
printf("%d\n", Max);
int i = pos, cnt = ;
for(i = pos; i != pre[i]; i = pre[i]) {
ans[++cnt] = i;
}
ans[++cnt] = i;
for(i = cnt; i >= ; --i) {
printf("%d\n", ans[i]);
}
return ;
}

最新文章

  1. .NET面试题系列[5] - 垃圾回收:概念与策略
  2. 读书笔记--SQL必知必会08--使用函数处理数据
  3. 无法启动调试。未安装Silverlight Developer运行时。最新运行时可以从以下地址下载: http://go.microsoft.com/fwlink/?LinkId=146060.
  4. 不再为Apache进程淤积、耗尽内存而困扰((转))
  5. struts2 CVE-2012-0838 S2-007 Remote Code Execution &amp;&amp; Hotfix
  6. SerialChat与Arduino的配合使用
  7. dubbo 转
  8. 第二章 rabbitmq在mac上的安装
  9. 【Energy Big Data】能源互联网和电力大数据
  10. mysql----快速删除数据表(drop,truncate.delete)
  11. UNIX网络编程——TCP连接的建立和断开、滑动窗口
  12. 「SDOI2018」物理实验
  13. jquery的datatables第二次加载报错
  14. redis 执行操作时提示(error) NOAUTH Authentication required.
  15. [HNOI2002] 营业额统计
  16. 小议常被忽略的a标签:visited属性的特殊用法
  17. 解决 pycharm can not save setting
  18. (转)CentOS 7 —— /etc/rc.local 开机不执行 - 解决方法
  19. Hive0.13.1介绍及安装部署
  20. linux bash命令行基本操作

热门文章

  1. Storm的容错性
  2. UITableView中的(NSIndexPath *)indexPath
  3. Servlet生命周期以及获取参数
  4. web服务器的相关资料 ngix
  5. HDU 4741
  6. HttpWebRequest代理访问网站
  7. vim的保存误认为utf8问题
  8. oracle sql语句跟踪
  9. GitHub的代码托管和使用方法
  10. [Papers]MHD, $\p_3\pi$, Lebesgue space [Jia-Zhou, JMAA, 2012]