数学考试

这是个水题...就是涉及的就是前缀。
下面讲讲思路首先我先分析下数据肯定是T*N解决嘛...
题目要你求两段序列长度为k的数最大和..很容易联想到利用前缀cnm[i]=sum[i]-sum[i-k]记录每个k段和的值..我的cnm[i]就是i-k+1~i的和然后利用一个pos数组记录当前位子cnm[i]值的最大值..因为我的思路就是枚举后一个数然后取前面的最大值,想想是不是我现在的值加上前面合法区间就是答案了,然后用ans更新下就好了..
代码:

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 132913423039
typedef long long ll;
const ll mod=1e9+7;
const ll N=2e5+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x){ return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
ll pos[N];//记录1~当前最大的值
ll sum[N];
ll cnm[N];
ll a[N];
int main()
{
    ios;
    ll t,n,k;
    cin>>t;
    while(t--)
    {
        ll cnt=-inf,ans=-inf;
        cin>>n>>k;
        for(ll i=1;i<=n;i++) {sum[i]=0,cnm[i]=0,pos[i]=0;}
        for(ll i=1;i<=n;i++) cin>>a[i],sum[i]+=(sum[i-1]+a[i]);
        for(ll i=k;i<=n;i++) cnm[i]=sum[i]-sum[i-k];//前面到这个点k个数的和
        for(ll i=k;i<=n;i++) {if(cnm[i]>cnt) cnt=cnm[i];pos[i]=cnt;}
        for(ll i=2*k;i<=n;i++) ans=max(cnm[i]+pos[i-k],ans);
        cout<<ans<<endl;
    }
    return 0;
}