摘要：
BZOJ_1915如果我们将一对相邻的通过格视为研究对象，那么相邻研究对象之间的距离不应超过K，相邻研究对象间的所有正格都可以在向前跳跃的过程中通过。抽象成这样的模型后，我们可以使用单调队列+dp来找到位置i处最后一个研究对象的最优解。此时，在向前跳的过程中，有可能通过最右侧的一些不超过K-1的正格。最后，扫描dp的最优解并将这些格相加。
BZOJ_1915
如果我们把一对相邻的来去经过的格子看成一个研究对象的话，那么相邻研究对象之间距离不超过K，而且相邻研究对象之间所有正数的格子都可以在向前跳的过程中经过。抽象成这样的模型之后就可以用单调队列+dp搞定最后一个研究对象在位置i时的最优解。这时由于在向前跳的过程中还可能经过最右边研究对象的右边的一些距离不超过K-1的正数的格子，最后扫一遍dp出的最优解，将这些格子一并加起来即可。
#include<stdio.h> #include<string.h> #include<algorithm> #define MAXD 250010 #define inf 0xc3c3c3c3c3c3c3c3ll typedef long long LL; int a[MAXD], N, K, q[MAXD]; LL A[MAXD], dp[MAXD]; void init() { A[0] = 0; for(int i = 1; i <= N; i ++) { scanf("%d", &a[i]); A[i] = A[i - 1]; if(a[i] > 0) A[i] += a[i]; } } void solve() { if(K == 1) { printf("%d\n", std::max(0, a[1])); return ; } int front = 0, rear = 0; memset(dp, 0xc3, sizeof(dp[0]) * (N + 1)); dp[0] = 0; for(int i = 2; i <= N; i ++) { while(front < rear && dp[q[rear - 1]] - A[q[rear - 1]] <= dp[i - 2] - A[i - 2]) -- rear; q[rear ++] = i - 2; while(front < rear && q[front] < i - K) ++ front; dp[i] = dp[q[front]] + a[i] + a[i - 1] + A[i - 2] - A[q[front]]; } LL ans = std::max(0ll, A[K]); for(int i = 1; i <= N; i ++) { int j = std::min(N, i + K - 1); ans = std::max(ans, dp[i] + A[j] - A[i]); } printf("%lld\n", ans); } int main() { while(scanf("%d%d", &N, &K) == 2) { init(); solve(); } return 0; }