考虑动归，在第i点时，在i-k到i中肯定有一个点j不能选择，即：j为断点。

所以f[i]=max(f[i],f[j-1]+a[j+1]+a[j+2]……a[i])（i-k<=j<=i） 所以维护前缀和，然后方程就变成了

f[i]=max(f[i],f[j-1]+sum[i]-sum[j]) (i-k<=j<=i)

变形一下变成： f[i]=max(f[i],f[j-1]-sum[j])+sum[i] (i-k<=j<=i)

发现max里面的值只与j有关，所以可以用单调队列优化转移。

又是没有数据的一题（艹）

赶紧加数据吧

又是没有数据的一题（dog）

数据不翼而飞

😕 😕 😕

考虑动归，在第i点时，在i-k到i中肯定有一个点j不能选择，即：j为断点。

所以f[i]=max(f[i],f[j-1]+a[j+1]+a[j+2]……a[i])（i-k<=j<=i） 所以维护前缀和，然后方程就变成了

f[i]=max(f[i],f[j-1]+sum[i]-sum[j]) (i-k<=j<=i)

变形一下变成： f[i]=max(f[i],f[j-1]-sum[j])+sum[i] (i-k<=j<=i)

发现max里面的值只与j有关，所以可以用单调队列优化转移。