首页 > 代码库 > [BZOJ 1046] [HAOI2007] 上升序列 【DP】
[BZOJ 1046] [HAOI2007] 上升序列 【DP】
题目链接：BZOJ - 1046
题目分析
先倒着做最长下降子序列，求出 f[i]，即以 i 为起点向后的最长上升子序列长度。
注意题目要求的是 xi 的字典序最小，不是数值！
如果输入的 l 大于最长上升子序列长度，输出 Impossible。
否则，从 1 向 n 枚举，贪心，如果 f[i] >= l，就选取 a[i]，同时 --l，然后继续向后找比 a[i] 大的第一个数判断是否 f[i] >= l （这时l已经减小了1）。
代码
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>using namespace std;const int MaxN = 10000 + 5;int n, m, l, MaxL;int T[MaxN];struct ES { int Num, Pos, w, v;} E[MaxN];inline bool CmpNum(ES e1, ES e2) { if (e1.Num == e2.Num) return e1.Pos < e2.Pos; return e1.Num < e2.Num;}inline bool CmpPos(ES e1, ES e2) { return e1.Pos < e2.Pos;}inline void Add(int x, int Num) { for (int i = x; i <= n; i += i & -i) T[i] = max(T[i], Num);}inline int Get(int x) { if (x == 0) return 0; int ret = 0; for (int i = x; i; i -= i & -i) ret = max(ret, T[i]); return ret;}int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &E[i].Num); E[i].Pos = i; } sort(E + 1, E + n + 1, CmpNum); int v_Index = 0; for (int i = 1; i <= n; ++i) { if (i == 1 || E[i].Num > E[i - 1].Num) ++v_Index; E[i].v = v_Index; } sort(E + 1, E + n + 1, CmpPos); MaxL = 0; for (int i = n; i >= 1; --i) { E[i].w = Get(n - (E[i].v + 1) + 1) + 1; MaxL = max(MaxL, E[i].w); Add(n - E[i].v + 1, E[i].w); } scanf("%d", &m); for (int i = 1; i <= m; ++i) { scanf("%d", &l); if (l > MaxL) { printf("Impossible\n"); continue; } int x = 0; for (int j = 1; j <= n; ++j) { if (E[j].v <= x) continue; if (E[j].w >= l) { x = E[j].v; --l; printf("%d", E[j].Num); if (l > 0) printf(" "); else break; } } printf("\n"); } return 0;}
[BZOJ 1046] [HAOI2007] 上升序列 【DP】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。