本文共 1171 字，大约阅读时间需要 3 分钟。
http://acm.hdu.edu.cn/showproblem.php?pid=1160
题意：现给出老鼠的体重与速度，要求你找出符合要求的最长子序列。
要求是 W[m[1]] < W[m[2]] < ... < W[m[n]]（体重） && S[m[1]] > S[m[2]] > ... > S[m[n]] （速度）
分析：有两个变量的话比较不好控制，自然需要先排序。再仔细思考的话，觉得和之前做的防御导弹有点类似，都是求最多能有几个符合条件的。思考到这，能 求出来了，然后再记录路径就可以了
#include #include #include #include #include #include #include #include #include #include using namespace std;#define INF 0x3f3f3f3fconst int maxn = 4007;typedef long long LL;int a[maxn], dp[maxn];struct node{ int w, v, sign, h;}s[maxn];///按照体重从大到小的顺序排序，若体重相同，按照速度从小到大排序bool cmp(node p, node q){ if(p.w == q.w) return p.v q.w;}int main(){ int k=1; while(scanf("%d %d", &s[k].w, &s[k].v)!=EOF) { s[k].h = k; s[k].sign = -1; k++; } sort(s+1, s+k+1, cmp); int ans = 0; for(int i=1; i s[j].v) { if(dp[j]+1>=dp[i]) { dp[i] = dp[j]+1; s[i].sign = j;///标记路径 } } if(dp[i]>dp[ans]) ans = i; } } printf("%d\n", dp[ans]); while(s[ans].sign!=-1) { printf("%d\n", s[ans].h); ans = s[ans].sign; } printf("%d\n", s[ans].h); return 0;}
转载于:https://www.cnblogs.com/daydayupacm/p/5744298.html
