http://acm.hdu.edu.cn/showproblem.php?pid=1160

同样是先按它的体重由小到大排,相同就按speed排就行。

这样做的好处是,能用O(n^2)枚举,因为前面的肯定不能和后面的搭配了。

然后就是LIS的题了,

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
struct node {
int weight, speed;
int id;
node(int a, int b, int c) : weight(a), speed(b), id(c) {}
node() {}
bool operator < (const struct node & rhs) const {
if (weight != rhs.weight) return weight < rhs.weight;
else return speed > rhs.speed;
}
}a[maxn];
struct DP {
int val;
struct node cur;
int pre;
}dp[maxn];
bool isok(struct node a, struct node b) {
if (a.weight < b.weight && a.speed > b.speed) return true;
else return false;
}
bool isbetter(struct node a, struct node b) {
if (a.weight != b.weight) return a.weight < b.weight;
else if (a.speed != b.speed) return a.speed > b.speed;
return false;
}
void show(int id) {
if (id == -inf) return;
show(dp[id].pre);
printf("%d\n", a[id].id);
}
void work() {
int total = ;
int c, d;
while (scanf("%d%d", &c, &d) != EOF) {
++total;
a[total] = node(c, d, total);
}
sort(a + , a + + total);
for (int i = ; i <= total; ++i) {
dp[i].val = ;
dp[i].pre = -inf;
dp[i].cur = a[i];
for (int j = ; j < i; ++j) {
if (isok(dp[j].cur, dp[i].cur)) { // i能接在j后面
if (dp[i].val < dp[j].val + ) {
dp[i].val = dp[j].val + ;
dp[i].pre = j;
} else if (dp[i].val == dp[j].val + ) {
if (isbetter(a[j], a[dp[i].pre])) { //j比它前一个好
dp[i].pre = j;
}
}
}
}
}
int ans = -inf;
int id;
for (int i = ; i <= total; ++i) {
if (ans < dp[i].val) {
ans = dp[i].val;
id = i;
}
}
printf("%d\n", ans);
show(id);
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
work();
return ;
}

最新文章

  1. 页面元素坐标和偏移(clientX/pageX/screenX/layerX/offsetWidth/scrollWidth/clientWidth等)相关整理
  2. javascript 创建对象的7种模式
  3. Codeforces Round #243
  4. [python]初探socket
  5. IOS 网络浅析(一 网络监测~Reachability)
  6. 统一事件源epoll代码示例
  7. 社区发现算法问题&amp;&amp;NetworkX&amp;&amp;Gephi
  8. cookie机制
  9. 【解题报告】瑞士轮(NOIP2011普及组T3)
  10. c++判断一个字符串是否是数字
  11. jsp --- jquery
  12. v-cloak的用法和注意事项
  13. 分布式协调服务Zookeeper扫盲篇
  14. logback root level logger level 日志级别覆盖?继承?
  15. 判断文件是否存在,不要用if exist和if not exist,因为他们会受到文件是否隐藏的影响,改用dir /a 命令代替
  16. str int list tuple dict 一些实操
  17. Python自动化开发 - 模块与包
  18. java http post上传文件
  19. Nagios学习笔记
  20. “全栈2019”Java异常第三章:try代码块作用域详解

热门文章

  1. Posix线程编程指南(2)
  2. SpringBoot 版本升级后报错 Cannot instantiate interface org.springframework.context.ApplicationContextInitializer
  3. CSS实现简单无缝滚动
  4. python+ mysql存储二进制流的方式
  5. Jenkins远程执行shell出现java: command not found
  6. deprecated conversion from string constant to ‘char*’
  7. Oracle查看表空间和表空间中的对象
  8. CodeForces 485A Factory (抽屉原理)
  9. MS SQL的CASE...WHEN...THEN...END语法
  10. [UE4]C++静态加载问题:ConstructorHelpers::FClassFinder()和FObjectFinder()