【数学考试】

数学考试

计 $dp[i]$ 为 $[i,n]$ 区间内，所有的 $[i-k,i]$ 这样的区间中，数之和的最大值。
那么只要遍历一遍，当左区间取 $[i-k,i]$ 时，右区间的最大值可以 $O(1)$ 读取，即 $dp[i+k]$ 。
所有以上计算均可以用前缀和达成 $O(n)$ 预处理。
完整代码如下：

#include
using namespace std;
#define ll long long
ll sum[422222],a[422222];
int main(){int t;cin>>t;while(t--){int n,k,i;cin>>n>>k;for(i=1;i<=n;i++)scanf("%lld",&a[i]);ll s=0;for(i=1;i<=n;i++){      //前缀和s+=a[i];sum[i]=s;}ll dp[222222]={0};   //dp[i]代表[i-k,i]到[n-k,n]这些所有的区间，和的最大值。ll ma=-1e18;for(i=n;i>=k;i--){ma=max(ma,sum[i]-sum[i-k]);dp[i]=ma;}ma=-1e18;for(i=k;i<=n-k;i++){ma=max(ma,sum[i]-sum[i-k]+dp[i+k]);}cout<<ma<<endl;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！