[HAOI2007]上升序列
发布日期:2021-08-21 13:17:54 浏览次数:14 分类:技术文章

本文共 783 字,大约阅读时间需要 2 分钟。

Description

Solution

一开始看成了是子序列的字典序最小,实际上是位置的字典序最小

先跑一边LIS,然后贪心的选最靠前的LIS够长的序列就行。

Code

由于一开始看错了,代码有点冗余。

const int N = 10010;int a[N], f[N], p[N], g[N], n;void main() {
n = read();
for (int i = 1; i <= n; ++i) a[i] = read();
memset(g, 0x3f, sizeof g);
for (int i = n; i; --i) {
for (int j = i + 1; j <= n; ++j)
if (a[j] > a[i]) {
if (f[j] > f[i]) f[i] = f[j], p[i] = j;
}
f[i]++;
g[f[i]] = i;
}
for (int i = n; i; --i) {
if (g[i] > g[i + 1]) g[i] = g[i + 1];
}
int q = read();
while (q--) {
int x = read();
if (x > n || g[x] == 0x3f3f3f3f)
puts("Impossible");
else {
for (int i = 1, last = 0, j = 1; i <= n && j <= x; ++i)
if (a[i] > last && f[i] >= x - j + 1) {
printf("%d ", a[i]);
j++;
last = a[i];
}
puts("");
}
}}

Note

要看清题啊!!!!

转载于:https://www.cnblogs.com/wyxwyx/p/bzoj1046.html

转载地址:https://blog.csdn.net/weixin_33720078/article/details/93684072 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:如何实现在已有代码之后添加逻辑之继承,组合(静态代理)实现方法
下一篇:剑指Offer:第一个只出现一次的字符

发表评论

最新留言

不错!
[***.144.177.141]2023年03月18日 03时29分00秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

c语言门铃设计实验报告,模拟电子技术课程设计实验报告 2019-12-06 20:23:43
c语言常用函数速查手册apk,c语言常用函数strcmp函数和strcpy函数 2019-12-06 20:23:43
c语言 java转换器,求助大神!!!JAVA转换成C语言 2019-12-06 20:23:43
linux c++ for i<0 循环,C++ for循环 2019-12-06 20:23:43
c语言调用串口扫码枪,C#利用控件mscomm32.ocx读取串口datalogic扫描枪数据 2019-12-06 20:23:43
labview c语言定义变量,第一章:LabVIEW 的编程环境 如何使用 VI 的重入属性(Reentrant)... 2019-12-06 20:23:44
linux编译安装openssh,RHEL6编译安装OpenSSH 2019-12-06 20:23:41
linux看安装了哪些函数,如何查看linux动态库中包含哪些函数 2019-12-06 20:23:42
allegro linux 安装教程,Linux上Centos系统知识图谱Allegrograph 6.6.0的安装方法和流程介绍... 2019-12-06 20:23:42
共创桌面linux,摒弃前嫌 KDE携手GNOME共创Linux桌面 2019-12-06 20:23:42
linux open函数功能,Linux系统文件I / O编程(1)--- open()和其他基本功能 2019-12-06 20:23:42
linux安装ruby环境 rvm,如何快速正确的安装 Ruby, Rails 运行环境 2019-12-06 20:23:42
宝塔Linux301重定向,宝塔面板如何设置301重定向(详细教程)! 2019-12-06 20:23:42
oracle 连接失去联系,插入大文件时c# – “ORA-03135:连接失去联系” 2019-12-06 20:23:40
linux服务器重启查询命令行,last命令查看系统重启状态(人工手动重启的还是系统内用命令重启的系统)... 2019-12-06 20:23:41
linux中kvm配置文件,如何在linux中通过kvm安装虚拟机 2019-12-06 20:23:41
linux内核5.6,在Deepin V20下可用命令来升级Linux内核到5.6版本以上 2019-12-06 20:23:41
linux svn服务器搭建 jb51,详解Linux服务器配置——搭建SVN服务器 2019-12-06 20:23:41
php处理 xss方法,php实现XSS安全过滤的方法 2019-12-06 20:23:39
oracle 查询最高分,SQL查找一个表里,每个班级的最高分。 2019-12-06 20:23:40