1 条题解
-
0
用f[i][j]表示位于第i行第j列时得到的最大分数，初始时f[1][j]=val(1,j)。
考虑上一秒在f[i-1][k]，那么因为移动速度最多为T，所以j-T≤k≤j+T。对于这个范围内的k，f[i][j]=p[i][j]+max{f[i-1][k]}。
这个部分可以用单调队列来优化，因为随着j增大，k的合法区间的两个端点都是右移的，用单调队列维护区间内f[i-1][k]的最大值。
核心代码
int pos = 0; tail = 0; head = 1; for (int j = 1; j <= m; j++) { while(pos + 1 <= m && pos + 1 <= j + t) { pos++; while (head <= tail && f[i-1][q[tail]] <= f[i-1][pos]) tail--; q[++tail] = pos; } while(head <= tail && q[head] < j - t) head++; f[i][j] = val[i][j] + f[i-1][q[head]]; }
- 1