浙农大第十九届程序设计竞赛 C-变强的秘药

变强的秘药

分析

确定这是一个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;
}