POJ1836 Alignment

知识点:最长单调子序列、分治

题目

有一支N个新兵的部队,他们的序号从左到右分别为1到N,每个新兵都有一个身高ai,现在,我们希望给这支部队尽量少的踢掉几个新兵,剩下的新兵靠拢,使得每个剩下的任意一个位置的新兵向左或者向右其中的某一边的身高是严格递减的。

输入

第一行输入一个N,表示新兵的个数(2≤N≤1000)。
第二行输入N个浮点数ai,分别表示这N个新兵的身高(0.5≤ai≤2.5)。

输出

输出一个整数,表示最少需要踢掉的新兵数目。

样例

input
6
0.7 1.9 1.6 1.9 1.6 0.7
output
1

提示

可以踢除第3个,然后使得前两个人的身高向左是严格递减的,后三个人的身高向右是严格递减的。
(笔者注:提示踢除人数有误)

思路

如果做过一般的最长单调子序列问题,很容易想到先求最长单调子序列,再将总人数减去最长单调子序列长度。
分析题意发现,如果踢掉新兵后的序列中有一个新兵的左端和右端都有比自己高的,那么这个序列不符合题意,说明只有左高右低、左低右高、左低右低三种可能,对于整个序列只可能有单调增、单调减、左部分单调增右部分单调减三种可能。对于第三种可能,可以通过取最长单调增子序列的左连续子序列与最长单调减子序列的右连续子序列连接,且前者在后者的左边实现。
实现思路见代码。

代码

#include"iostream"
#include"algorithm"
#define ll long long
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rev(i,a,b) for(ll i=a;i>=b;i--)
using namespace std;
const int maxn=1e3+10;
//dp1:0~i最长单调增子序列,dp2:i~n-1最长单调减序列
ll dp1[maxn],dp2[maxn];
//输入
double arr[maxn];

int main()
{
   
  ll n;
  cin>>n;
  rep(i,0,n) cin>>arr[i];
  //初始化最长为只有i位置的元素,长度为1
  rep(i,0,n) dp1[i]=dp2[i]=1;
  //dp 0~i最长单调增子序列
  rep(i,1,n) rep(j,0,i) if(arr[i]>arr[j]) dp1[i]=max(dp1[j]+1,dp1[i]);
  //dp i~n-1最长单调减序列
  rev(i,n-2,0) rev(j,n-1,i+1) if(arr[i]>arr[j]) dp2[i]=max(dp2[j]+1,dp2[i]);
  //初始化最大值为只取最左端和最右端两个元素
  ll ans=2;
  //dp[i]仅表示当前的最长序列,不代表在所有最长序列中最长,所以最长单调增子序列与最长单调减子序列不一定相邻,但因题意为先增后减,所以最长单调减子序列一定在最长单调增子序列的右边
  rep(i,0,n-1) rep(j,i+1,n) ans=max(dp1[i]+dp2[j],ans);
  //总人数减最长增减序列的个数为去掉的人数
  cout<<n-ans<<endl;

  return 0;
}
全部评论

相关推荐

#简历#先说一说我自己的想法,很多人都很排斥苍穹外卖,认为没什么技术点和含金量,但实际上我觉得恰恰相反,苍穹外卖虽然代码本身并不是你自身能力的证明,但是是作为一个新人学习时很好的跳板和原始框架,在这个框架上进行的改进可以很好的辐射到你自己的个人成果上,并作为你和面试官聊天的筹码大多数人的苍穹外卖只写增删改查,千篇一律,吸引不了面试官,所以这才让大家误以为只要是苍穹外卖就不要写进简历里这种误区,但实际上如果你在原有的层面上进行改进,并作为你的项目亮点和面试官介绍,告诉他你的苍穹外卖和别人的有什么不同,增加了哪些技术难点,这才显得你是完全自己理解了这个项目,并且有自己动手实践项目的能力,而不是就看了个课程就以为自己会了,就当成自己的了,如此一来,这反而成为你的加分项苍穹外卖为什么看的人最多,说明它好啊,如果它不好,为什么看的人还这么多,想清楚这个逻辑,我觉得要做的最重要的事,就是如何在原有框架上进行改进提效,比起听其他人的话重新搞一个项目性价比高得多,而且我亲测项目并没有成为我找到工作的阻碍,我投的大厂一大半都给我面试了,而且很多不止一个部门,退一万步说,当你手头没有其他项目的时候,有苍穹外卖总比什么都没有的好很多,不需要因为苍穹外卖有任何心理负担关于简历的任何部分都欢迎大家提意见,十分感谢大家,祝大家找实习+秋招顺利上岸,offer拿到手软#简历中的项目经历要怎么写##我的上岸简历长这样##最后再改一次简历##简历##简历被挂麻了,求建议#
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务