php网站带数据库,苏宁易购电子商务网站建设目标,传媒网站建设网,关于网站建设的软文题目链接#xff1a;BZOJ - 1046 题目分析 先倒着做最长下降子序列#xff0c;求出 f[i]#xff0c;即以 i 为起点向后的最长上升子序列长度。 注意题目要求的是 xi 的字典序最小#xff0c;不是数值#xff01; 如果输入的 l 大于最长上升子序列长度#xff0c;输出 Imp…题目链接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 algorithmusing 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;
}转载于:https://www.cnblogs.com/JoeFan/p/4250767.html
