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