题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1160
题意
给出一系列的 wi si
要找出一个最长的子序列 满足 wi 是按照升序排列的 si 是按照 降序排列的
思路 因为有双关键词
我们 可以先将一关键词 比如 W 按照 升序排序
再根据 S 关键词 来找 最长下降子序列 就可以了
要输出 其中的一个子序列 我们只要 记录 其 父节点就可以 再循环网上找
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e3 + 5; const int MOD = 1e9 + 7; struct node { int w, s; int id; }q[maxn]; bool comp(node x, node y) { if(x.w == y.w) return x.s > y.s; return x.w < y.w; } int dp[maxn]; int pre[maxn]; int main() { int pos = 1; while (~scanf("%d%d", &q[pos].w, &q[pos].s)) q[pos].id = pos++; sort(q, q + pos, comp); int ans = 1; CLR(dp, 0); CLR(pre, 0); for (int i = 1; i <= pos; i++) { dp[i] = 1; for (int j = 1; j < i; j++) { if (q[i].s < q[j].s && q[i].w > q[j].w) { if (dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; pre[i] = j; } } } ans = max(ans, dp[i]); } printf("%d\n", ans); vector <int> v; for (int i = 1; i <= pos; i++) { if (dp[i] == ans) { int vis = i; v.pb(q[vis].id); while (pre[vis]) { v.pb(q[pre[vis]].id); vis = pre[vis]; } break; } } vector <int>::iterator it; for (it = v.end(), it--; ; it--) { printf("%d\n", *it); if (it == v.begin()) break; } }转载于:https://www.cnblogs.com/Dup4/p/9433113.html
