codeforces-Ed92-B

codeforces-Ed92-B

七月 30, 2020

B. Array Walk

题意
有n<1e5个格子每个位置有一个val>0

从1号位置跳格子每次跳到一个格子i获得格子的val[i]

可以向左或向右跳前提是不超或边界

最初有sum=val[1]

现在限制跳k次,最多不能往左跳z次且不能连续向左跳

问最大得分

题解

一定是在某两个数之间反复横跳 或者直接走到底 最大

不会这里来回跳之后在其他位置再来回跳 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
ll data[Max];
ll sum[Max];
int num[10];
/*
 
*/
int main() {
    Turnoff;
    int t;cin>>t;
    while(t--){
        int n,k,z;cin>>n>>k>>z;
        z=min(z,k/2);
        //priority_queue<int,vector<int>,less<int> >q;
        for(int i=1;i<=n;i++){
            cin>>data[i];
            //if(i>1)q.push(data[i]+data[i-1]);
            sum[i]=sum[i-1]+data[i];
            //cout<<sum[i]<<" ";
        }
        //cout<<endl;
        ll ans=0,last=k+1;
        //cout<<data[last]<<endl;
        for(int i=last;i>1;i--){
            ll temp=sum[i];
            int turn=last-i;
            int left=(turn+1)/2;
            if(left>z){
                temp+=data[i-1]*z+data[i]*z;
                temp+=sum[k-2*z+1]-sum[i];
                ans=max(ans,temp);
            }
            else{
                temp+=data[i-1]*left+data[i]*(turn-left);
                ans=max(ans,temp);
 
            }
            //cout<<i<<" "<<temp<<" "<<ans<<endl;
        }
        cout<<ans<<endl;
    }
}