【牛客7872 C变强的秘药】dp

题意

给n个数，按这个n个数给出的顺序取数，每一次至少取k个数，每一次取数的==收益==是取的序列后三个数之积 - 前三个数之积。例如我本次取a[1]~a[10]，我能得到的收益是a[10] * a[9] * a[8] - a[1] * a[2] * a[3]。求怎么取能获得最大收益？

题解

dp[i]代表以 i 为取的某一次的右端点时，答案的最大值是多少。那么我们求的就是dp[n]，因为显而易见n一定是某一次取的右端点。
考虑这个答案是由几部分组成的
是由3部分组成的，首先第一部分是 $a[i] * a[i-1] * a[i-2]$ ，这一部分是雷打不动的
那另外两部分就是与 $i$ 相对于的这一次的左端点 $j$ 会带来的收益 $-a[j]*a[j+1]*a[j+2]$ 以及dp[j-1]
由于第一部分是雷打不动的，所以想要让 $dp[i]$ 尽可能大，只能让 $dp[j-1]-a[j]*a[j+1]*a[j+2]$ 这一部分尽可能大
也就是需要枚举一个左端点j，求出上式的最大值即可
由于n的数据范围是1e7,因此上述做法显然是 $n^2$ 的做法，优化一下就是，一边更新dp值，一边维护我们想要的这个最大值，即可优化成O(n)的

需要注意的是，我们转移时用到的 $dp[j-1]，dp[j-1]$ 就代表着 $j-1$ 是某一次取的右端点，又由于每一次至少取k个，所以， $j-1$ 必须>k，所以 $i-k$ 必须 $>k$ 才能开始维护我们想要的那个最大值，一开始维护值应该初始化为-a[1] * a[2] * a[3]

Code

/****************************
* Author : W.A.R            *
* Date : 2020-10-30-19:58   *
****************************/
/*
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<set>
#define IOS ios::sync_with_stdio(false)
#define show(x) std:: cerr << #x << " = " << x << std::endl;
#define mem(a,x) memset(a,x,sizeof(a))
#define Rint register int
using namespace std;
typedef long long ll;
const int maxn=1e7+100;

ll dp[maxn],a[maxn];
int main(){
    int n,k;scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}
    ll res=-a[1]*a[2]*a[3];
    for(int i=k;i<=n;i++){
        if(i-k>=k)res=max(res,dp[i-k]-a[i-k+1]*a[i-k+2]*a[i-k+3]);
        dp[i]=res+a[i]*a[i-1]*a[i-2];
    }
    printf("%lld\n",dp[n]);
    return 0;
}