2020牛客暑期多校训练营(第五场)D 思维|最长上升子序列
发布日期:2022-03-30 18:18:17
浏览次数:36
分类:博客文章
本文共 1285 字,大约阅读时间需要 4 分钟。
Drop Voicing
题目链接:
题目描述:
给定一个n个数的序列,你可以对序列进行两种操作
操作1:将当前序列的倒数第二个元素放置在序列首部,即a1,a2,a3,,,,aN变为a1,an-1,a2,a3,,,aN
操作2:将当前序列的首部元素放置在序列尾部:即a1,a2,a3,,,aN变为a2,a3,,,aN,a1
操作2不限次数,不算操作,连续的多次进行操作1被视为一次操作,问最少需要多少次操作可以将序列转换为上升序列
思路:
可以把这个序列看成一个环,操作2可以理解成转动这个环,对当前序列元素的相对位置并无影响,由操作2我们可以得到该序列的n种排列,然后对于每种排列我们求它的LIS(最长上升子序列),当前序列的LIS代表了这个序列不需要改动位置的元素,剩下的每个元素的位置改动需要经过数次操作1后即可达到目的。所以结果就是序列长度减去所有排列种最大的LIS。
多次操作1的实质是:可以将一个数转移到任意一个位置
代码:
#includeusing namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();int main(){ int n; vector v; cin>>n; for(int i = 1; i <= n; i++){ int x; cin>>x; v.push_back(x); } int ans = 0; for(int i = 0; i < n; i++){ vector low,now; int cnt = 0,j = i; while(cnt low[low.size()-1]){ low.push_back(now[j]); }else{ vector ::iterator ite = upper_bound(low.begin(),low.end(),now[j]); if(ite==low.end()){ low.push_back(now[j]); }else *ite = now[j]; } } int res = low.size(); ans = max(ans,res); } cout< <
转载地址:https://www.cnblogs.com/cloudplankroader/p/13378198.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年03月10日 11时31分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
php读取大文件某行内容,PHP读取和修改大文件的某行内容_PHP教程
2019-04-21
打印php错误日志,php怎样打印错误日志
2019-04-21
mysql中用户线程作用,mysql用户线程的建立与用户线程的状态源码解析
2019-04-21
php页面引用公共文件,WeiPHP插件模板中快速引入公共模板文件
2019-04-21
php tracy,admin.php
2019-04-21
php访问父类的所有属性,php – 在父类中使用$this仅在子类中显示父类属性
2019-04-21
oracle比较强大的函数,SQL和ORACLE函数比较
2019-04-21
php把整数拆分成数组,数组拆分处理(整数时的处理),该怎么处理
2019-04-21
php红包平均分配,红包平均分配算法
2019-04-21
linux磁盘的命令是,linux磁盘相关的命令
2019-04-21
linux 停用用户,linux – 如何禁用用户的网络访问?
2019-04-21
linux服务器 缓存,Linux服务器内存使用分析及内存缓存
2019-04-21