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 ;
}