【每日一题】3月27日每日一题题解(dp+前缀和）

题意：求两段连续不相交的长度为k的序列的和的最大值。
思路：dp+前缀和。
定义状态：dp[i]为[1,i]区间内所有长度为k的区间的最大值。
那么当我们枚举到区间[i+1,i+k+1]时，我们把这个区间作为右区间,然后他的左区间里的最大值也就是[1,i]里的最大值。
就是dp[i],可以通过O(1)的时间得到。所以复杂度就足够了。
注意点：当我们从k开始枚举的时候,我们先记录k的dp,然后从k+1开始枚举，这样子当所有数都为负数时，也还是可以成功dp。不然很显然,dp的原始值0比负数大,就不能成功dp了，见代码。

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<math.h>
#include<stack>
#include<map>
#include<limits.h>
#include<vector>
#include<string.h>
#include<string>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 2*1e5+5;
const int M = 10007;
#define pi acos(-1)
#define INF 1e8
#define INM INT_MIN
#define pb(a)  push_back(a)
#define mk(a,b) make_pair(a,b)
#define dbg(x) cout << "now this num is " << x << endl;
#define met0(axx) memset(axx,0,sizeof(axx));
#define metf(axx) memset(axx,-1,sizeof(axx));
#define sd(ax) scanf("%d",&ax)
#define sld(ax) scanf("%lld",&ax)
#define sldd(ax,bx) scanf("%lld %lld",&ax,&bx)
#define sdd(ax,bx) scanf("%d %d",&ax,&bx)
#define sddd(ax,bx,cx) scanf("%d %d %d",&ax,&bx,&cx)
#define sfd(ax) scanf("%lf",&ax)
#define sfdd(ax,bx) scanf("%lf %lf",&ax,&bx)
#define pr(a) printf("%d\n",a)
#define plr(a) printf("%lld\n",a)
LL dp[N],sum[N],a[N];/
int main()
{
    int t,n,k;
    sd(t);
    while(t--)
    {
        met0(sum);
        met0(dp);
        sdd(n,k);
        for(int i=1;i<=n;++i) sld(a[i]),sum[i] = sum[i-1]+a[i];
        dp[k] = sum[k];//第一个特殊化，不然当都是-1时就会是0.
        for(int i=k+1;i<=n;++i)
        {
            dp[i] = max(dp[i-1],sum[i]-sum[i-k]);
        }
        LL ans = dp[k]+sum[2*k]-sum[k];//第一个特殊化,和上面类似,或者让ans为一个无穷小的数
        for(int i=k+1;i<=n-k;++i)//枚举右区间
        {
            ans = max(ans,dp[i]+sum[i+k]-sum[i]);
        }
        plr(ans);
    }   
    system("pause");
    return 0;
}