【BZOJ1046】[HAOI2007]上升序列
2024-09-03 00:41:13
【BZOJ1046】[HAOI2007]上升序列
题面
题解
\(dp\)完之后随便搞一下即可,注意不要看错题
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 1e4 + 5;
int N, a[MAX_N], dp[MAX_N];
int main () {
N = gi(); for (int i = 1; i <= N; i++) a[i] = gi();
reverse(&a[1], &a[N + 1]);
fill(&dp[1], &dp[N + 1], 1);
for (int i = 1; i <= N; i++)
for (int j = 1; j < i; j++)
if (a[j] > a[i]) dp[i] = max(dp[i], dp[j] + 1);
int mx = 1;
for (int i = 1; i <= N; i++) mx = max(mx, dp[i]);
int M = gi();
while (M--) {
int l = gi();
if (l > mx) { puts("Impossible"); continue; }
else {
int now = 0;
for (int i = N; i >= 1; i--)
if (dp[i] >= l && a[i] > now) {
printf("%d ", a[i]);
now = a[i], --l;
if (!l) break;
}
printf("\n");
}
}
return 0;
}
最新文章
- easy_UI 投票列表
- Spring4.X——搭建
- Linux安装Node.js
- C++虚函数和虚函数表
- WIFI功率修改
- HTML-正则表达式
- NOI2012 : 迷失游乐园
- java 的文件读取操作
- (转)Android之自定义适配器
- 打造自己的程序员品牌(摘自Infoq)
- 在mac上访问自带服务器权限问题
- 基于visual Studio2013解决面试题之1402选择排序
- Windows入门基础:1.关于CreateWindow()函数使用中遇到的问题
- vim 编辑中执行正则表达式
- [转载] Solr使用入门指南
- android galley实现画廊效果
- javascript中的in运算符
- (最完美)红米手机5的Usb调试模式在哪里打开的教程
- [转]Centos 查看端口占用情况和开启端口命令
- UVa140 Bandwidth 【最优性剪枝】