鱼C论坛

 找回密码
 立即注册
查看: 1928|回复: 0

[技术交流] 003:士兵站队

[复制链接]
发表于 2018-2-6 00:26:48 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 Messj 于 2018-6-8 23:36 编辑

[POJ 1836] 士兵站队 (Alignment)

题目描述

在军队中,一个团是由士兵组成的。在早晨的检阅中,士兵们在长官面前站成一行。但长官对士兵们的队列并不满意。士兵们的确按照他们的编号由小到大站成一列,但并不是按高度顺序来站的。于是,长官让一些士兵出列,其他留在队里的士兵没有交换位置,变成了更短的一列。这个队列满足一下条件:队伍里的每一个士兵都至少可以看见整个队伍的最前方或最后方,(如果一个士兵要看到队伍的最前方或最后方,那么在他的前方或后方,都没有比他高的人)。

现在按顺序给出一个队列里的每个士兵的身高,计算出若要形成满足上述条件的队列,长官至少需要让多少士兵出列。

输入

输入数据的第一行,包含一个整数n,表示原队列里士兵的数量。第二行,包含n个浮点数(最多有五位小数),第i个浮点数表示队列中编号为i的士兵的身高hi。

其中:2 <= n <= 1000 ,且身高hi的取值范围[0.5,2.5]。

输出

包含一个整数,表示需要出列的最少士兵数。

样例输入       
8
1.86 1.86 1.30621 2 1.4 1 1.97 2.2
样例输出
4


解析

这道题嘛,就是让队列里最少的士兵出列,使队列变成这么一个样子,如图-1。由于要求最少出列人数,也就是保留最多人数,于是这道题就有了求最长上升子序列的DP做法。对第i个人,计算1~i的最长上升序列(长度为l)与i+1~n的最长下降序列(长度为d),对所有的i,取l+d的最大值max。答案即为n-max。二分+枚举也可求解。


DP解法:
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1001;
int n;
double num[maxn];
int up[maxn],down[maxn];

int main()
{
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
                scanf("%lf",&num[i]);
                up[i]=1;down[i]=1;
        }
        int ans=0;        
        for(int i=0;i<n;i++)
        {
                for(int j=0;j<i;j++)
                {
                        if(num[i]>num[j])
                        {
                                if(up[i]<(up[j]+1))
                                        up[i]=up[j]+1;
                        }
                }
        }
        
        for(int i=n-1;i>=0;i--)
        {
                for(int j=n-1;j>i;j--)
                {
                        if(num[i]>num[j])
                        {
                                if(down[i]<(down[j]+1))
                                        down[i]=down[j]+1;
                        }
                }
        }
        
        for(int i=0;i<n-1;i++)
        {
                for(int j=i+1;j<n;j++)
                        ans=max(ans,up[i]+down[j]);
        }
        printf("%d\n",n-ans);
}

二分+枚举
#include <cstdio>  
#include <algorithm>  
using namespace std;  
int const MAX = 1e3 + 5;  
int const INF = 0x3fffffff;  
int l[MAX], r[MAX];  
double lstk[MAX], rstk[MAX];  
double h[MAX];  
  
int main()  
{  
    int n, ltop = 0, rtop = 0;  
    scanf("%d", &n);  
    for(int i = 1; i <= n; i++)  
    {  
        scanf("%lf", &h[i]);  
        if(h[i] > lstk[ltop])  
            lstk[++ ltop] = h[i];  
        else  
        {  
            int low = 1, high = ltop, mid;  
            while(low <= high)  
            {  
                mid = (low + high) >> 1;  
                if(h[i] > lstk[mid])  
                    low = mid + 1;  
                else  
                    high = mid - 1;  
            }  
            lstk[low] = h[i];  
      
        }  
       l[i] = ltop;  
    }  
    for(int i = n; i >= 1; i--)  
    {  
        if(h[i] > rstk[rtop])  
            rstk[++ rtop] = h[i];  
        else  
        {  
            int low = 1, high = rtop, mid;  
            while(low <= high)  
            {  
                mid = (low + high) >> 1;  
                if(h[i] > rstk[mid])  
                    low = mid + 1;  
                else  
                    high = mid - 1;  
            }  
            rstk[low] = h[i];  
        }  
        r[i] = rtop;     
    }  
    int in = 0;  
    for(int i = 1; i < n; i++)  
        for(int j = i + 1; j <= n; j++)  
            in = max(in, (l[i] + r[j]));  
    printf("%d\n", n - in);  
}  

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-6 09:31

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表