题解：SP7741 BOI7SEQ - Sequence

· · 题解

简单贪心

贪心策略

显然，这道题直接写出最优解是困难的，所以我们可以反过来，求最劣解，也就是

\max_{1\le i\le n} a_i \times (n-1)

再反回来，要使得最优，我们最多只能让最大值左边或右边的一个数只和它进行一次操作，再分治，直到区间长度为二即可。最后发现只需要两两枚举，求出最大值之和。

\sum_{i=2}^{n} \max \left ( a_i,a_{i-1} \right )

最终实现方法

我们发现，数组可以滚掉一维，用两个变量代替，大大降低了空间复杂度，时间复杂度为 \Theta \left ( n \right ) 。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
signed main(){
    int n,x,y,ans=0;
    cin>>n>>y;
    for(int i=2;i<=n;i++){
        cin>>x;
        ans+=max(x,y);
        y=x;
    }
    cout<<ans;
    return 0;
}//把数组滚掉了