题目描述

由于hyf长得实在是太帅了,英俊潇洒,风流倜傥,人见人爱,花见花开,车见车载。有一群MM排队看hyf。每个MM都有自己独特的风格,由于hyf有着一颗包容的心,所以,什么风格的MM他都喜欢……但是,hyf有一个特别的要求,他不希望总是看到风格得差不多的MM,更加特别的是,如果两个MM风格完全一样,hyf不会有任何意见。现在,hyf希望从去看他的MM中,去掉一些MM,从而使得相邻2个MM的风格值的差(绝对值)不为1。自然地,hyf希望去掉的MM越少越好。

输入格式

第一行一个整数N;

第2~N+1行N个整数,第i个为ci。表示第i个MM的风格值。

N≤1000 0 ≤ ci ≤ 2000

输出格式

一个数,表示最少要去掉的MM数。


要去掉的数最少,也就是求最长的满足条件的序列长度。

类似于LIS的做法,我们可以用dp求解。设dp(i)表示1~i满足条件的最长序列的长度。那么可以得出状态转移方程:

\[dp[i]=Max_{1≤j<i,|a[i]-a[j]|{\neq}1}{\{}dp[j]+1{\}}
\]

目标状态为dp(n)。

时间复杂度为O(N^2)。


然而dp并不是最优解,我们可以进行优化。

显然,只有当a(j)=a(i)-1或者a(j)=a(i)+1两种位置不能够进行转移。所以为了保证有解,我们只需要记三个值即可:1~i-1的dp前三大的值,并再记下其所对应的a数组的值。那么三个值里面至少一个能够对dp(i)进行转移,并且转移过来也是最优值。

时间复杂度为O(N)。

#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 2001
#define inf 0x3f3f3f3f
using namespace std; int n,a1=-inf,a2=-inf,a3=-inf,dp1,dp2,dp3; inline int read(){
register int x(0),f(1); register char c(getchar());
while(c<'0'||'9'<c){ if(x=='-') f=-1; c=getchar(); }
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
inline int Abs(const int &x){ return x<0?-x:x; } int main(){
n=read();
for(register int i=1;i<=n;i++){
int cur=read(),len;
if(Abs(cur-a3)!=1) len=dp3+1;
if(Abs(cur-a2)!=1) len=dp2+1;
if(Abs(cur-a1)!=1) len=dp1+1;
if(cur==a1) dp1=len;
else if(cur==a2) dp2=len;
else if(cur==a3) dp3=len;
else if(len>dp3) a3=cur,dp3=len;
if(dp1<dp2) swap(dp1,dp2),swap(a1,a2);
if(dp1<dp3) swap(dp1,dp3),swap(a1,a3);
if(dp2<dp3) swap(dp2,dp3),swap(a2,a3);
}
printf("%d\n",n-dp1);
return 0;
}

最新文章

  1. XF custom render 各平台实现类
  2. Ruby数组
  3. Java 批量插入数据(Oracle)
  4. python学习笔记-Day6(2)
  5. chrome扩展程序开发之在目标页面运行自己的JS
  6. 基于 SquashFS 构建 Linux 可读写文件系统
  7. poj1023
  8. 擅长排列的小明 II(找规律)
  9. Kill命令模拟1
  10. FairScheduler的任务调度机制——assignTasks
  11. poj 3013 Big Christmas Tree (dij+优先级队列优化 求最短)
  12. IL反编译的实用工具
  13. 如何使用python生成xml
  14. ABP入门系列(6)——定义导航菜单
  15. C#中内嵌资源的读取
  16. [Linux]使用awk批量杀进程的命令
  17. 基于jeesite的cms系统(七):GlobalException全局异常和部署
  18. newcoder-最长树链-树/gcd
  19. Mybatis-spring 动态代理
  20. mysql基础讲解

热门文章

  1. Python朗读excel中的英文单词
  2. 让vs2013自带的IISExpress支持apk文件下载
  3. 使用h5开发跨平台APP确保数据安全交互---服务器篇
  4. 【命令】kill命令
  5. Next.js+React聊天室|Next仿微信桌面端|next.js聊天实例
  6. c#——ToString()的各种用法
  7. 腾讯云联合多家生态伙伴,重磅开源 SuperEdge 边缘容器项目
  8. SM4
  9. SQL数据库创建,创建表,增删改查
  10. SQL语句实现增删改查