【HAOI 2007】 上升序列
2024-08-30 19:07:00
【题目链接】
【算法】
先预处理 : 将序列反转,求最长下降子序列
对于每个询问,根据字典序性质,贪心即可
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10010 int i,j,len,n,q,mx,pre,l;
int a[MAXN],f[MAXN];
vector<int> res; template <typename T> inline void read(T &x)
{
int f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
template <typename T> inline void write(T x)
{
if (x < )
{
putchar('-');
x = -x;
}
if (x > ) write(x/);
putchar(x%+'');
}
template <typename T> inline void writeln(T x)
{
write(x);
puts("");
} int main() { read(n);
for (i = ; i <= n; i++) read(a[i]);
reverse(a+,a+n+);
for (i = ; i <= n; i++)
{
f[i] = ;
for (j = i - ; j >= ; j--)
{
if (a[i] < a[j])
f[i] = max(f[i],f[j]+);
}
mx = max(mx,f[i]);
} read(q);
while (q--)
{
read(l);
if (l > mx)
{
puts("Impossible");
continue;
} else
{
res.clear();
pre = ;
for (i = n; i >= ; i--)
{
if (f[i] >= l && a[i] > pre)
{
res.push_back(a[i]);
l--;
pre = a[i];
}
if (!l) break;
}
len = res.size();
for (i = ; i < len - ; i++)
{
write(res[i]);
putchar(' ');
}
writeln(res[len-]);
}
}
return ; }
最新文章
- Object-C与Swift混编
- Xcode6 管理provisioning profile
- data-role参数表:
- 功放AUX接口解析
- 推荐一个很棒的JS绘图库Flot
- JVM 1.类的加载、连接、初始化
- Android中使用WebView, WebChromeClient和WebViewClient加载网页 (能够执行js)
- 你会做Web上的用户登录功能吗?
- Linux下JDK安装
- VMware的安装和使用
- 设计模式,Let&#39;s “Go”! (下)
- Linux 下Beanstalk安装
- java泛型基础、子类泛型不能转换成父类泛型
- Ngui使用随心记
- ES6定型数组
- 微软Power BI 每月功能更新系列——7月Power BI 新功能学习
- T-SQL 带参数存储过程
- [Luogu5162]WD与积木(多项式求逆)
- ES5 方法学习
- Linux杂技
热门文章
- CodeForces - 750D New Year and Fireworks
- iOS - 设置系统类似的方法弃用警告的方式
- Codeforces 659B Qualifying Contest【模拟,读题】
- Ubuntu 16.04关闭Alt+鼠标左键移动窗口(转)
- InfoQ中文站特供稿件:Rust编程语言的核心部件
- MVC+ZTree实现对树的CURD及拖拽操作
- Oracle可插拔数据库的jdbc连接串写法
- 2016/05/25 empty() 与 isset()的区别
- 2016/04/13 ①html 中各种分割线------------------------------------------ ② 控制文字显示
- npm, webpack, vue-cli, vue-x, axios