poj1836 C-Alignment (简单dp)

思路来源

https://blog.csdn.net/yeguxin/article/details/47393305?utm_source=blogxgwz0

题意

给一个序列，代表士兵身高。

现要求不改变士兵位置的情况下，

让一些士兵出列，使原身高函数呈单峰函数。

问出列士兵最少是多少。

ps:单峰函数，即对于任意一个士兵i，i都能望到队列的左端或队列的右端。

题解

就是一个最长单增子序列+最长下降子序列。

up[i]，代表0号到i号的最长单增子序列的长度，

down[i+1]，代表(i+1)号到(n-1)号的最长单减子序列的长度。

up[i]+down[i+1]即保留在队列中的人数。

枚举士兵i（0<=i<=n-1）作为峰顶，则0号到i号单增，(i+1)号到(n-1)号单减。

注意单独判断一下i=-1和i=n的情况，即全增或全降的情况。

最长单增子序列：lower_bound

最长不降子序列：upper_bound

最长单减和最长不增，即reverse(a,a+n)即可，求反串的单增和不降。

浮点数小数点后五位，乘1e5变整数，怕被卡精度。

代码

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const int INF=0x3f3f3f3f;
const int maxn=1e5+10; 
const int mod=1e9;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
int n,ans,len,dp[1005],b[1005],up[1005],down[1005];
double a[1005];
void solve()
{
	len=0;ans=n;
	mem(dp,INF);
	rep(i,0,n-1)
	{
	  *lower_bound(dp,dp+n,b[i])=b[i];
	  up[i]=lower_bound(dp,dp+n,INF)-dp;//以i为结尾的LIS 
        }
	reverse(b,b+n);
	mem(dp,INF);
	rep(i,0,n-1)
	{
	  *lower_bound(dp,dp+n,b[i])=b[i];
	  down[n-1-i]=lower_bound(dp,dp+n,INF)-dp;
        }
        len=max(len,down[0]);//只降 
        rep(i,0,n-2)len=max(len,up[i]+down[i+1]);
	len=max(len,up[n-1]);//只升 
        ans=n-len;
}
int main()
{  
   sci(n);
   rep(i,0,n-1)
   {
    sclf(a[i]);
    b[i]=a[i]*100000;
   }
   solve();
   printf("%d\n",ans);
   return 0;
}