luogu P3411 序列变换
2024-09-04 07:40:52
链接 P3411 序列变换
- 如果要最小化答案,那么就最大化不移动的数。
- 那么不移动的子序列一定是最后答案的一段连续区间,而移动的数我们是一定有办法把他们还原的。
- 设\(f_{i}\)表示\(i\)点的最长长度,转移实际上是恒定的,即\(f_{i}=f_{j}+1\),其中\(j\)是\(i\)的前驱且唯一确定。
- 把\(a\)数组离散化后直接查值域即可,复杂度\(O(nlogn)\)。
#include<bits/stdc++.h>
#define R register int
using namespace std;
const int N=1000001;
int n,Mx,ans,len,O[N],vis[N],f[N],w[N],T[N];
int gi(){
R x=0,k=1;char c=getchar();
while(c!='-'&&(c<'0'||c>'9'))c=getchar();
if(c=='-')k=-1,c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*k;
}
int main(){
n=gi();
for(R i=1;i<=n;++i)w[i]=gi(),O[i]=w[i];
sort(O+1,O+n+1),len=unique(O+1,O+n+1)-O-1;
for(R i=1;i<=n;++i){
w[i]=lower_bound(O+1,O+len+1,w[i])-O;
if(!vis[w[i]])f[i]=T[w[i]-1]+1;
else f[i]=T[w[i]]+1;
vis[w[i]]=1,T[w[i]]=f[i],ans=max(ans,f[i]);
}
cout<<n-ans<<endl;
return 0;
}
最新文章
- android include进来的组件 调用其子元素
- JavaScript - 对象
- 表单验证——JavaScript和Jquery版
- CSSOM视图模式(CSSOM View Module)相关整理(转载)
- 把Nginx加为系统服务(service nginx start/stop/restart)
- POJ3126 Prime Path
- intent.addFlags(Intent.FLAG_ACTIVITY_NO_HISTORY);
- canvas 背景填充
- Linux中处理需要传输的IP报文流程
- Android Binder机制原理(史上最强理解,没有之一)(转)
- LOJ#6285. 数列分块入门 9
- 【译】第九篇 SQL Server安全透明数据加密
- boost 随机数发生器
- mybatis分页 -----PageHelper插件
- as3.0拼图
- 贪心算法HURUST题目
- Linux命令_用户身份切换
- swift 错误集锦
- php内存回收机制的学习
- Notes of Daily Scrum Meeting(11.19)
热门文章
- android 摇一摇功能的实现
- 线段树板子1(洛谷P3372)
- Illegal modifier for parameter *** , only final is permitted”
- python字典小知识
- sync_binlog innodb_flush_log_at_trx_commit 深入理解
- Varint数值压缩存储方法
- [Python3 填坑] 006 “杠零”,空字符的使用
- [BZOJ 2989]数列(CDQ 分治+曼哈顿距离与切比雪夫距离的转化)
- centos解决Could not find a version that satisfies the requirement pip3 (from versions: none)及No matching distribution found for pip3问题
- Django - Xadmin (五) POP