看清题目很重要 以i为界限,他的左右最大的长度为k的连续子段为状态,转移方程很容易推出
m[i]=max(m[i+1],sum[i+k]-sum[i])///i右边
M[i]=max(M[i-1],sum[i]-sum[i-k]);///i左边
就是一个经典的dp
注意数据范围
a[i]可以小于0还有边界位置处理
请在这里输入引用内容
输入描述:
第一行一个整数T(T<=10),代表有T组数据
接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <= n)
接下来一行n个整数a1,a2,...,an,(-100,000<=ai<=100,000)
输出描述:
输出一个整数,qwb能获得的最大分数
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=4e5+7; int a[maxn]; int m[maxn];///右边 int M[maxn];///左边 int sum[maxn];///前缀和 signed main() { int t; cin>>t; while (t--) { int n,k; cin>>n>>k; sum[0]=0; fill(m+1,m+n-k+1,-1e7); fill(M+k,M+n+1,-1e7);///数据开小点 for (int i=1;i<=n;++i) { cin>>a[i]; sum[i]=sum[i-1]+a[i]; } m[n-k]=sum[n]-sum[n-k]; for (int i=n-k-1;i>=1;--i) { m[i]=max(m[i+1],sum[i+k]-sum[i]); } M[k]=sum[k]; for (int i=k+1;i<=n;++i) { M[i]=max(M[i-1],sum[i]-sum[i-k]); } int all=-1e15;///坑点 和可能小于0 for (int i=k;i<=n-k;++i) { all=all>(M[i]+m[i])?all:(M[i]+m[i]); } cout<<all<<endl; } return 0; }