Crybl @ 2019-03-16 11:50:56
求助各位大佬,这段代码为什么第一个点答案一样,还过不去... 第一个点 5 2 1 2 3 4 5 output 12
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN =1e6+10;
ll f[MAXN][2]={0},n,k,sum[MAXN]={0};
int main()
{
ll a,ans=0;
cin>>n>>k;
for(int i=1;i<=n;++i)
cin>>a,sum[i]=sum[i-1]+a;
for(int i=1;i<=n;++i)
{
f[i][0]=max(f[i-1][0],f[i-1][1]);
for(int j=i-k;j<i;++j)
f[i][1]=max(f[i][1],f[j][0]+sum[i]-sum[j]);
}
ans=max(f[n][0],f[n][1]);
cout<<ans;
return 0;
}
by Crybl @ 2019-03-16 11:52:35
然后如果把后面f[i][1]的转移换成单调队列的话,就可以ac...求助各位大佬...
by 3493441984zz @ 2019-03-16 11:56:35
后面是