本文主要是介绍uva 10131 最长子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给大象的体重和智商，求体重按从大到小，智商从高到低的最长子序列，并输出路径。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>#define LL long longusing namespace std;
const int maxn = 1e3 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = 4 * atan(1.0);
const double ee = exp(1.0);struct Elephant
{int w;int iq;int r;
} e[maxn];bool cmp(Elephant a, Elephant b)
{return a.w > b.w;
}int dp[maxn];
int n;
int path[maxn];
int ans;void print(int i, int dep)
{if (dep == ans)return;printf("%d\n", e[i].r);print(path[i], dep + 1);//printf("%d\n", e[i].r);
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALn = 1;while (scanf("%d%d", &e[n].w, &e[n].iq) != EOF){e[n].r = n;n++;}sort(e + 1, e + n + 1, cmp);dp[0] = 0;for (int i = 1; i < n; i++){// cout << e[i].w << " " <<e[i].iq << " " << e[i].r << endl;dp[i] = 1;path[i] = i;for (int j = 1; j < i; j++){if (e[i].iq > e[j].iq && dp[i] < dp[j] + 1 && e[i].w < e[j].w){dp[i] = dp[j] + 1;path[i] = j;}}}ans = -1;int pos = 0;for (int i = 1; i < n; i++){if (ans < dp[i]){pos = i;ans = dp[i];}}printf("%d\n", ans);print(pos, 0);return 0;
}
这篇关于uva 10131 最长子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
