问题标题: 酷町堂：4362 最广山脉

Question

0

已解决

荣光峰

资深光能

看到这题，我第一反应————不会。

于是写了个暴力，拿了20......

（我居然没超时）

有没有大佬告诉我具体思路啊，求求了。

荣光峰在2021-08-05 17:40:53追加了内容

ding

荣光峰在2021-08-06 07:57:37追加了内容

ding

荣光峰在2021-08-06 13:21:35追加了内容

ding

荣光峰在2021-08-07 10:15:28追加了内容

ding

酷町豆刷题求解 C++ 0条评论 2 年，9 月前

Answer 1

已采纳

汪恺恒

中级启示者

注意看题，它说山脉必须连续。

所以，f[i]和g[i]两个数组只能由f[i-1]和g[i-1]推导出来

f数组推导：

for(int i=1;i<=n;i++){
        if(a[i]>a[i-1]) f[i]=f[i-1]+1;
        else f[i]=1;
    }

g数组和统计答案自己写

Answer 2

梁怡墨

新手守护

int n,a[1000005],l[1000005],r[1000005];
int main(){
   cin>>n;
   for(int i=0;i<n;i++){
       cin>>a[i];
       l[i]=1;
       r[i]=1;
   }
   for(int i=1;i<n;i++){
       for(int j=0;j<i;j++){
           if(a[j]<a[i]){
               l[i]=max(l[i],l[j]+1);
           }
       }
   }
   for(int i=n-2;i>=0;i--){
       for(int j=n-1;j>i;j--){
           if(a[j]<a[i]){
               r[i]=max(r[i],r[j]+1);
           }
       }
   }
   int s=l[0]+r[0];
   for(int i=1;i<n;i++){
       if(l[i]+r[i]>s){
           s=l[i]+r[i];
       }
   }
   cout<<s-1;

呜呜呜，超时

Answer 3

汪子晨

修练者

这头像~

Answer 4

王文博

缔造者之神

火车头+黑科技或者scanf可以有效避免超时（针对杜大佬的）

Answer 5

杜承俊

资深守护

超时代码

#include<bits/stdc++.h>
using name** std;
int a[1010],b[1010],c[1010],n,mx=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
b[i]=1;
for(int j=1;j<i;j++)
if(a[i]>a[j]) b[i]=max(b[i],b[j]+1);
} for(int i=n;i>=1;i--){
c[i]=1;
for(int j=n;j>=i+1;j--)
if(a[i]>a[j])
c[i]=max(c[i],c[j]+1);
}
for(int i=1;i<=n;i++)
mx=max(b[i]+c[i]-1,mx);
cout<<n-mx;
}
AC代码时用到二分的，你应该没学

问题标题: 酷町堂：4362 最广山脉

5 个回答: