【HDOJ】1160 FatMouse's Speed

DP。

 #include <stdio.h>
#include <string.h>
#include <stdlib.h> #define MAXNUM 1005 typedef struct {
int w, s;
int index;
} mouse_st; mouse_st mouses[MAXNUM];
int dp[MAXNUM], next[MAXNUM]; int comp(const void *a, const void *b) {
mouse_st *p = (mouse_st *)a;
mouse_st *q = (mouse_st *)b;
if (p->w == q->w)
return p->s - q->s;
else
return q->w - p->w;
} int main() {
int n=, m, beg;
int i, j, max, index; while (scanf("%d %d", &mouses[n].w, &mouses[n].s) != EOF) {
mouses[n].index = n;
++n;
} memset(dp, , sizeof(dp));
qsort(mouses, n, sizeof(mouse_st), comp);
for (i=; i<n; ++i)
next[i] = i;
m = ; for (i=; i<n; ++i) {
max = ;
for (j=; j<i; ++j) {
if (mouses[j].w>mouses[i].w && mouses[j].s<mouses[i].s) {
if (max < dp[j]) {
max = dp[j];
index = mouses[j].index;
}
}
}
if (max)
next[mouses[i].index] = index;
dp[i] = max + ;
if (m < dp[i]) {
m = dp[i];
beg = mouses[i].index;
}
}
if (m == )
printf("1\n1\n");
else {
printf("%d\n", m);
while (next[beg] != beg) {
printf("%d\n", beg+);
beg = next[beg];
}
printf("%d\n", beg+);
} return ;
}
上一篇:mac 环境下adb的安装


下一篇:go-hbase的Scan模型源码分析