变强的秘药

分析

确定这是一个dp,设f[i]为吃完前i个秘药能增加的最大码力值,先写出暴力的转移方程

   memset(f,-0x3f,sizeof(f));f[0]=0;
   for (int i=k;i<=n;i++)
       for (int j=i-k;j>=0;j--)
           f[i]=max(f[i],f[j]+a[i]*a[i-1]*a[i-2]-a[j+1]*a[j+2]*a[j+3]);

可以发现,当我们确定了一个i之后,图片说明 是不变的,如果要求最大,那么图片说明 就得最大。那不就完了吗?我们用一个数组p,令图片说明 ,然后每次更新因为要连续k个要一起吃,所以转移方程
图片说明
同时还有一些细节处理,具体看代码

代码

#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

using namespace std;

const int N=1e7+10;

int n,k;
ll f[N],a[N],p[N];

int main()
{
    memset(f,-0x3f,sizeof(f));f[0]=0;

    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);

    p[0]=-a[1]*a[2]*a[3];
    for (int i=1;i<k;i++) p[i]=p[i-1];
    for (int i=k;i<=n;i++)
    {
        f[i]=a[i]*a[i-1]*a[i-2]+p[i-k];
        p[i]=max(p[i-1],f[i]-a[i+1]*a[i+2]*a[i+3]);
    }

    printf("%lld\n",f[n]);

    return 0;
}