【暑训排位 #8 A】动态规划 LIS

In the army, a platoon is composed by n soldiers. During the morning inspection, the soldiers are aligned in a straight line in front of the captain. The captain is not satisfied with the way his soldiers are aligned; it is true that the soldiers are aligned in order by their code number: 1 , 2 , 3 , . . . , n , but they are not aligned by their height. The captain asks some soldiers to get out of the line, as the soldiers that remain in the line, without changing their places, but getting closer, to form a new line, where each soldier can see by looking lengthwise the line at least one of the line’s extremity (left or right). A soldier see an extremity if there isn’t any soldiers with a higher or equal height than his height between him and that extremity.

Write a program that, knowing the height of each soldier, determines the minimum number of soldiers which have to get out of line.

Input

On the first line of the input is written the number of the soldiers n. On the second line is written a series of n floating numbers with at most 5 digits precision and separated by a space character. The k-th number from this line represents the height of the soldier who has the code k (1 <= k <= n).

There are some restrictions:

• 2 <= n <= 1000

• the height are floating numbers from the interval [0.5, 2.5]

Output

The only line of output will contain the number of the soldiers who have to get out of the line.

Sample Input

8

1.86 1.86 1.30621 2 1.4 1 1.97 2.2

Sample Output

4

题意：一排人，通过挑出一些人，可以从纵向的左或右看到每个人，问最少挑出多少个

思路：

要达到“从左往右”和“从右往左”看能覆盖所有人，其实就是下面三种情况：

1.从左到右递增，然后从左边看，每个人都能被看到

2.从右往左递增，然后从右边看，每个人都能被看到

3.从左向右递增到某个位置i，从右边往左递增到某个位置j，然后从左往右看能看到第i个人，从右往左看能看到第j个人（倒着数）。同样覆盖了所有人。

然后发现其实情况3覆盖了前面两种，第一种情况就是i=j=n，第二种情况就是i=j=1。所以我们只需要左右求一个最长上升子序列，然后看dp1[i] + dp2[j]即可（若是同一个点要-1）。然后用n-ans即是输出。

AC代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e3+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline int read(){ int f = 1; int x = 0;char ch = getchar();while(ch>'9'|ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

double dp1[maxn];
double dp2[maxn];
double a[maxn];
double len1[maxn];
double len2[maxn];

int main()
{
    int n;
    while(cin>>n)
    {
        mem(dp1,0); mem(dp2,0);
        mem(len1,0);mem(len2,0);
        rep(i,1,n) cin>>a[i];
        int maxlen = 1;
        dp1[maxlen] = a[1];
        rep(i,1,n)
        {
            if(a[i] > dp1[maxlen]) dp1[++maxlen] = a[i], len1[i] = maxlen;
            else
            {
                int idx = lower_bound(dp1+1, dp1+1+maxlen, a[i]) - dp1;
                dp1[idx] = a[i];
                len1[i] = idx;
            }

        }
        maxlen = 1;dp2[maxlen] = a[n];
        per(i,n,1)
         {
              if(a[i] > dp2[maxlen]) dp2[++maxlen] = a[i], len2[i] = maxlen;
              else
              {
                  int idx = lower_bound(dp2+1,dp2+1+maxlen,a[i]) - dp2;
                  dp2[idx] = a[i];
                  len2[i] = idx;
              }
         }
         ll ans = 0;
         rep(i,1,n) rep(j,i,n) ans = max(ans,len1[i] + len2[j] - (i==j));
         cout<< n - ans<<'\n';
    }
    return 0;
}