POJ1836-Alignment

来源:互联网 时间:1970-01-01

转载请注明出处:優YoU http://user.qzone.qq.com/289065406/blog/1300076744

解题思路:是POJ2533的扩展题。

题意不难,令到原队列的最少士兵出列后,使得新队列任意一个士兵都能看到左边或者右边的无穷远处。就是使新队列呈三角形分布就对了。

 

但这里有一个陷阱,看了一些别人的解题报告说“任一士兵旁边不能存在等高的士兵”,然后又举了一个例子说注意

3

5 5 5

的情况,我没看他们的程序,不知道他们是不是把这些例子特殊处理了,但完全没必要,因为“允许处于三角形顶部的两个士兵等高”,图形化就是如下图:


 

其实蓝色士兵的身高和红色士兵的身高是完全没有关系的。

 

要求最少出列数,就是留队士兵人数最大,如图,即左边的递增序列人数和右边的递减序列人数之和最大

因而可转化为求“最长不降子序列”和“最长不升子序列”问题

 

但是不能直接套用LIS思想,因为这题不允许任一侧的序列中出现等高士兵

 

基本操作方法:

对士兵的身高数组逐一进行枚举,枚举到的k值作为蓝色士兵,k+1值作为红色士兵,以这两个士兵分别作为最长不降子序列L1的终点和最长不升子序列L2的起点,即作为整个队列的分界点。

然后分别对两边进行dp,枚举到某一个m值时,使得L1+L2的长度为最大max,此时用总士兵人数n 减去max就是  最少出列人数

 

本题不能使用LISO(n^2)常规算法,因为一旦应用到本题,由于队列存在两段序列,要对分界点进行枚举,会导致整体时间复杂度上升到O(n^3),绝对TLE超时

本题只能用LISO(n*logn)算法,具体算法步骤直接看LIS的相关介绍就有了,这里不再重复。需要注意的是要使用不同的二分法查找LISLDS序列,还要注意在二分查找记录数组ord[ ]时,搜索的起点和终点位置,详细可以看我的程序。

最后就是要注意LISLDS长度,还有ord的初始化(程序中我是直接释放,再重新申请的)、边界问题,全部在我的程序中都有详细体现。

 

 

我再给出一些数据:

Sample Input

12

0.9 0.8 0.7 1 0.6 0.5 1.1 1.2 1.3 1.4 1.5 1.6

5

1 1 1 1 1

5

1 1.5 2 1.5 1

8

3 4 5 1 2 5 4 3

3

5 5 5

3

5 5 4

4

5 5 4 6

 

Sample Output

4

3

0

3

2

1

2

 1 //Memory Time 
2 //232K 391MS
3
4 //O(n*logn)算法,注意LIS和LDS使用不同的二分法
5 #include<iostream>
6 using namespace std;
7 const int inf=3;
8
9 //ord[]为不降序列
10 //二分法搜索digit,若str中存在digit,返回其下标
11 //若不存在,返回str中比digit小的最大那个数的(下标+1)
12 int binary_search_1(double ord[],double digit,int head,int length)
13 {
14 int left=head,right=length;
15 int mid;
16 while(right!=left)
17 {
18 mid=(left+right)/2;
19 if(digit==ord[mid])
20 return mid;
21 else if(digit<ord[mid])
22 right=mid;
23 else
24 left=mid+1;
25 }
26 return left;
27 }
28
29 //ord[]为不升序列
30 //二分法搜索digit,若str中存在digit,返回其下标
31 //若不存在,返回str中比digit大的最小那个数的(下标+1)
32 int binary_search_2(double ord[],double digit,int head,int length)
33 {
34 int left=head,right=length;
35 int mid;
36 while(right!=left)
37 {
38 mid=(left+right)/2;
39 if(digit==ord[mid])
40 return mid;
41 else if(digit>ord[mid])
42 right=mid;
43 else
44 left=mid+1;
45 }
46 return left;
47 }
48
49 int main(int i,int j)
50 {
51 int n; //士兵数
52 while(cin>>n)
53 {
54 double* h=new double[n+1];
55
56 for(i=1;i<=n;i++)
57 cin>>h[i];
58
59 int max=0;
60 for(int m=1;m<=n;m++) //对身高队列每一个值作为分界点,进行枚举
61 {
62 double* ord=new double[n+1];
63
64 /*Dp-(0~m)-LIS*/
65
66 ord[0]=-1; //下界无穷小
67 int len_LIS=1;
68 for(i=1;i<=m;i++)
69 {
70 ord[len_LIS]=inf; //上界无穷大
71 j=binary_search_1(ord,h[i],0,len_LIS);
72 if(j==len_LIS) //sq[i]大于ord最大(最后)的元素
73 len_LIS++;
74 ord[j]=h[i];
75 }
76 len_LIS--; //减去ord[0]的长度1
77
78 /*Dp-(m+1~n)-LDS*/
79
80 ord[m]=inf; //下界无穷大
81 int len_LDS=1;
82 for(i=m+1;i<=n;i++)
83 {
84 ord[m+len_LDS]=-1; //上界无穷小
85 j=binary_search_2(ord,h[i],m,m+len_LDS);
86 if(j==m+len_LDS) //sq[i]大于ord最小(最后)的元素
87 len_LDS++;
88 ord[j]=h[i];
89 }
90 len_LDS--; //减去ord[m]的长度1
91
92 //max为对于当前m的 最长不升子序列LIS 和 最长不降子序列LDS 长度之和
93
94 if(max<len_LIS+len_LDS)
95 max=len_LIS+len_LDS;
96
97 delete ord;
98 }
99
100 cout<<n-max<<endl;
101
102 delete h;
103 }
104 return 0;
105 }
我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b我的新浪微博:http://weibo.com/lyy289065406我的腾讯微博:http://t.qq.com/liao5422我的QQ空间:http://user.qzone.qq.com/289065406我的百度空间:http://hi.baidu.com/you289065406/home我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


相关阅读:
Top