Educational Codeforces Round 92 (Rated for Div. 2)B. Array Walk(枚举)

地址：http://codeforces.com/contest/1389/problem/B

题意：

长度为n的a[]，规定走k步，最多z次向左走。不能连续向左走。求获得的最大分数。

解析：

看z范围就知道，可以对z进行枚举，找到每次的落脚点，直接算分数即可。

需要反复横跳的地点，是最大的相邻和值，所以用p[]进行记录。

sum[]来记录前缀和。

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<string.h>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=1e5+20;
int a[maxn],sum[maxn],p[maxn];
int main()
{

    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k,z;
        cin>>n>>k>>z;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
            p[i]=max(a[i]+a[i-1],p[i-1]);
        }
        int ans=sum[k+1];
        int all=min(k/2,z);
        for(int i=0;i<=all;i++)
        {
            int r=k+1-2*i;　　//落脚点
            int md=sum[r]+i*p[r+1];　　//p[r+1]的原因，虽然r是落脚点，但是有可能左右横跳的地点在r到r+1处并最后回到了r点。
            ans=max(ans,md);
        }
        cout<<ans<<endl;
    }    
}