N层楼，每层M个有分数的格子，一开始在第一层的S点，每层最多不能连续走T个就必须下楼，求到达最底层能获得的最大分数。
经典的单调队列优化问题，用A[i][j]表示前缀和，now表示当前层，pre表示上一层，可以得到以下递推式：
当前层从左向右走，d[now][i]=max(d[pre][j]+A[now][i]-A[now][j-1]) = max((d[pre][j]-A[now][j-1])+A[now][i]) (j<=i)
当前层从右向左走，d[now][i]=max(d[pre][j]+A[now][j]-A[now][i-1]) = max((d[pre][j]+A[now][j])-A[now][i-1]) (j>i)
括号中的项为单调队列中的比较值，然后d[now][i]取从左和从右走的最大值即可。
1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 #include <algorithm> 5 #define INF 0x3f3f3f3f 6 using namespace std; 7 int n, m, x, tt; 8 int mz[105][10005]; 9 int d[10005], t[10005]; 10 int q[10005], front, rear; 11 int main(){ 12 //freopen("test.in","r",stdin); 13 while (scanf("%d%d%d%d", &n, &m, &x, &tt) != EOF) { 14 for (int i = 1; i <= n; i++) 15 for (int j = 1; j <= m; j++) 16 scanf("%d", &mz[i][j]), mz[i][j] += mz[i][j-1]; 17 for (int i = 1; i <= m; i++) { 18 if (abs(i-x) > tt) d[i] = -INF; 19 else d[i] = x>i ? mz[1][x] - mz[1][i-1] : mz[1][i] - mz[1][x-1]; 20 } 21 for (int i = 2; i <= n; i++) { 22 front = rear = 0; 23 for (int j = 1; j <= m; j++) t[j] = d[j] + mz[i][j] - mz[i][j-1]; 24 for (int j = 1; j <= m; j++) { 25 while (front < rear && j - q[front] > tt) front++; 26 if (front < rear) t[j] = max(t[j], d[q[front]] + mz[i][j] - mz[i][q[front]-1]); 27 while (front < rear && d[q[rear-1]] - mz[i][q[rear-1]-1] < d[j] - mz[i][j-1]) --rear; 28 q[rear++] = j; 29 } 30 front = rear = 0; 31 for (int j = m; j >= 1; j--) { 32 while (front < rear && q[front] - j > tt) front++; 33 if (front < rear) t[j] = max(t[j], d[q[front]] + mz[i][q[front]] - mz[i][j-1]); 34 while (front <rear && d[q[rear-1]] + mz[i][q[rear-1]]< d[j] + mz[i][j]) --rear; 35 q[rear++] = j; 36 } 37 for (int j = 1; j <= m; j++) d[j] = t[j]; 38 } 39 int ans = 0; 40 for (int i = 1; i <= m; i++) ans = max(ans, d[i]); 41 printf("%d\n", ans); 42 } 43 return 0; 44 }