做设计学什么英语比较好的网站,体育新闻最新消息,广州建网站费用,全渠道营销成功案例有一排人#xff0c;身高可能不同#xff0c;现在有一个理想状态是这排的每个人向左或向右看没有被挡住视野(当遇到等高或更高的人时会被挡住)#xff0c;现在问最少让几人出列可以达到这个理想状态。 最少人出列#xff0c;其实就是一个人数最多的理想状态。求一个人数最多…有一排人身高可能不同现在有一个理想状态是这排的每个人向左或向右看没有被挡住视野(当遇到等高或更高的人时会被挡住)现在问最少让几人出列可以达到这个理想状态。 最少人出列其实就是一个人数最多的理想状态。求一个人数最多的类似山峰的高度排列。那就可以从左到右、从右到左各求一遍LIS 开始用 O(n2)的写法WA了错在搞错dp[i] 的含义dp[i]代表以i为尾的LIS最后输出答案时应该枚举 dp[i]dp[j] 1 #include cstdio2 #include algorithm3 using namespace std;4 5 int height[1024];6 int dp1[1024];//up7 int dp2[1024];//down8 9 int main(){
10 int N;
11 scanf(%d,N);
12 for(int i0;iN;i){
13 double tmp;
14 scanf(%lf,tmp);
15 height[i]tmp*1000000.1;
16 }
17 for(int i0;iN;i){
18 dp1[i]1;
19 for(int j0;ji;j){
20 if(height[j]height[i]) dp1[i]max(dp1[i],dp1[j]1);
21 }
22 }
23 for(int iN-1;i0;i--){
24 dp2[i]1;
25 for(int jN-1;ji;--j){
26 if(height[j]height[i]) dp2[i]max(dp2[i],dp2[j]1);
27 }
28 }
29 //for(int i0;iN;i) printf(i : %d\tup: %d , down: %d\n,i,dp1[i],dp2[i]);
30 int ans-1;
31 //ansmax(ans,dp2[0]);
32 //for(int i0;iN-1;i)ansmax(ans,dp1[i]dp2[i1]);
33 //ansmax(ans,dp1[N-1]);
34 for(int i0;iN;i)
35 for(int ji1;jN;j)
36 ansmax(ans,dp1[i]dp2[j]);
37 printf(%d\n,N-ans);
38 } View Code 用O(nlogn)的写法 1 #include cstdio2 #include algorithm3 using namespace std;4 5 const int INF0x3f3f3f3f;6 int height[1024];7 int dp1[1024];//up8 int dp2[1024];//down9 int S[1024];
10 int tot;
11
12 int B_S(int l,int r,int ob){
13 int mid;
14 r--;
15 while(lr){
16 mid(lr)1;
17 if(S[mid]ob) rmid-1;
18 else lmid1;
19 }
20 return l;
21 }
22
23 int main(){
24 int N;
25 scanf(%d,N);
26 for(int i0;iN;i){
27 double tmp;
28 scanf(%lf,tmp);
29 height[i]tmp*1000000.1;
30 }
31
32 fill(S,SN,INF);
33 for(int i0;iN;i){
34 int poslower_bound(S,SN,height[i])-S;
35 dp1[i]pos1;
36 S[pos]height[i];
37 }
38 fill(S,SN,INF);
39 for(int iN-1;i0;i--){
40 int poslower_bound(S,SN,height[i])-S;
41 dp2[i]pos1;
42 S[pos]height[i];
43 }
44 //for(int i0;iN;i) printf(i : %d\tup: %d , down: %d\n,i,dp1[i],dp2[i]);
45 int ans-1;
46 //ansmax(ans,dp2[0]);
47 //for(int i0;iN-1;i)ansmax(ans,dp1[i]dp2[i1]);
48 //ansmax(ans,dp1[N-1]);
49 for(int i0;iN;i)
50 for(int ji1;jN;j)
51 ansmax(ans,dp1[i]dp2[j]);
52 printf(%d\n,N-ans);
53 } View Code 1 #include cstdio2 #include algorithm3 using namespace std;4 5 int height[1024];6 int dp1[1024];//up7 int dp2[1024];//down8 int S[1024];9 int tot;
10
11 int B_S(int l,int r,int ob){
12 int mid;
13 r--;
14 while(lr){
15 mid(lr)1;
16 if(S[mid]ob) rmid-1;
17 else lmid1;
18 }
19 return l;
20 }
21
22 int main(){
23 int N;
24 scanf(%d,N);
25 for(int i0;iN;i){
26 double tmp;
27 scanf(%lf,tmp);
28 height[i]tmp*1000000.1;
29 }
30 tot0;
31 for(int i0;iN;i){
32 if(tot0||S[tot-1]height[i]) S[tot]height[i];
33 else{
34 //int posB_S(0,tot,height[i]);
35 int poslower_bound(S,Stot,height[i])-S;
36 S[pos]height[i];
37 }
38 dp1[i]tot;
39 }
40 tot0;
41 for(int iN-1;i0;i--){
42 if(tot0||S[tot-1]height[i]) S[tot]height[i];
43 else{
44 //int posB_S(0,tot,height[i]);
45 int poslower_bound(S,Stot,height[i])-S;
46 S[pos]height[i];
47 }
48 dp2[i]tot;
49 }
50 //for(int i0;iN;i) printf(i : %d\tup: %d , down: %d\n,i,dp1[i],dp2[i]);
51 int ans-1;
52 //ansmax(ans,dp2[0]);
53 //for(int i0;iN-1;i)ansmax(ans,dp1[i]dp2[i1]);
54 //ansmax(ans,dp1[N-1]);
55 for(int i0;iN;i)
56 for(int ji1;jN;j)
57 ansmax(ans,dp1[i]dp2[j]);
58 printf(%d\n,N-ans);
59 } View Code 一种单调栈一种从修改预设数组都是二分 开始一直在用upper_bound后来脑补跑数据才发现upper_bound只能用来找不下降子序列lower_bound是用来找严格上升子序列。转载于:https://www.cnblogs.com/Kiritsugu/p/9581702.html
