003：士兵站队
本帖最后由 Messj 于 2018-6-8 23:36 编辑士兵站队 (Alignment)
题目描述
在军队中，一个团是由士兵组成的。在早晨的检阅中，士兵们在长官面前站成一行。但长官对士兵们的队列并不满意。士兵们的确按照他们的编号由小到大站成一列，但并不是按高度顺序来站的。于是，长官让一些士兵出列，其他留在队里的士兵没有交换位置，变成了更短的一列。这个队列满足一下条件：队伍里的每一个士兵都至少可以看见整个队伍的最前方或最后方,(如果一个士兵要看到队伍的最前方或最后方，那么在他的前方或后方，都没有比他高的人)。
现在按顺序给出一个队列里的每个士兵的身高，计算出若要形成满足上述条件的队列，长官至少需要让多少士兵出列。
输入
输入数据的第一行，包含一个整数n，表示原队列里士兵的数量。第二行，包含n个浮点数(最多有五位小数)，第i个浮点数表示队列中编号为i的士兵的身高hi。
其中：2 <= n <= 1000 ，且身高hi的取值范围。
输出
包含一个整数，表示需要出列的最少士兵数。
样例输入
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;
int up,down;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lf",&num);
up=1;down=1;
}
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(num>num)
{
if(up<(up+1))
up=up+1;
}
}
}
for(int i=n-1;i>=0;i--)
{
for(int j=n-1;j>i;j--)
{
if(num>num)
{
if(down<(down+1))
down=down+1;
}
}
}
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
ans=max(ans,up+down);
}
printf("%d\n",n-ans);
}
二分+枚举
#include <cstdio>
#include <algorithm>
using namespace std;
int const MAX = 1e3 + 5;
int const INF = 0x3fffffff;
int l, r;
double lstk, rstk;
double h;
int main()
{
int n, ltop = 0, rtop = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%lf", &h);
if(h > lstk)
lstk[++ ltop] = h;
else
{
int low = 1, high = ltop, mid;
while(low <= high)
{
mid = (low + high) >> 1;
if(h > lstk)
low = mid + 1;
else
high = mid - 1;
}
lstk = h;
}
l = ltop;
}
for(int i = n; i >= 1; i--)
{
if(h > rstk)
rstk[++ rtop] = h;
else
{
int low = 1, high = rtop, mid;
while(low <= high)
{
mid = (low + high) >> 1;
if(h > rstk)
low = mid + 1;
else
high = mid - 1;
}
rstk = h;
}
r = rtop;
}
int in = 0;
for(int i = 1; i < n; i++)
for(int j = i + 1; j <= n; j++)
in = max(in, (l + r));
printf("%d\n", n - in);
}
页:
[1]