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;
}