这题我有闪过是用单调队列优化的想法，也想过有左右两边各烧一遍。 但是不敢确定，搜了题解，发现真的是用单调队列，然后写了好久，调了好久下标应该怎么变化才过的。
dp[i][j] 表示走到第i行，第j个竖线的最大价值。
dp[i][j] = max(dp[i-1][k]+pre[i][j-1]-pre[i][k-1]); 从左往右
dp[i][j] = max(dp[i][j],dp[i-1][k]+suf[i][j]-suf[i][k]); 从右往左
1 #pragma warning(disable:4996) 2 #pragma comment(linker, "/STACK:1024000000,1024000000") 3 #include <stdio.h> 4 #include <string.h> 5 #include <time.h> 6 #include <math.h> 7 #include <map> 8 #include <set> 9 #include <queue> 10 #include <stack> 11 #include <vector> 12 #include <bitset> 13 #include <algorithm> 14 #include <iostream> 15 #include <string> 16 #include <functional> 17 const int INF = 1 << 30; 18 typedef __int64 LL; 19 /* 20 dp[i][j]表示走到第i个横线，第j个竖线的最大值 21 dp[i][j] = max(dp[i-1][k] + sum[j-1] - sum[k-1]) 22 单调队列优化维护队首最大值， 23 */ 24 25 int q[11111], head, tail; 26 int dp[111][11111]; 27 int a[111][11111]; 28 int b[111][11111]; 29 int pre[111][11111], suf[111][11111]; 30 int sum1[111][11111]; 31 int sum2[111][11111]; 32 int main() 33 { 34 int n, m, k; 35 36 while (scanf("%d%d%d", &n, &m, &k),n+m+k) 37 { 38 memset(dp, 0, sizeof(dp)); 39 memset(pre, 0, sizeof(pre)); 40 memset(suf, 0, sizeof(suf)); 41 memset(sum1, 0, sizeof(sum1)); 42 memset(sum2, 0, sizeof(sum2)); 43 n++; 44 for (int i = 1;i <= n;++i) 45 { 46 for (int j = 1;j <= m;++j) 47 { 48 scanf("%d", &a[i][j]); 49 pre[i][j] = pre[i][j - 1] + a[i][j]; 50 suf[i][j] = a[i][j]; 51 } 52 for (int j = m;j >= 1;--j) 53 suf[i][j] += suf[i][j + 1]; 54 55 } 56 for (int i = 1;i <= n;++i) 57 { 58 for (int j = 1;j <= m;++j) 59 { 60 scanf("%d", &b[i][j]); 61 sum1[i][j] = b[i][j]; 62 sum2[i][j] = sum2[i][j - 1] + b[i][j]; 63 } 64 for (int j = m;j >= 1;--j) 65 sum1[i][j] += sum1[i][j + 1]; 66 } 67 for (int i = n;i >= 1;--i) 68 { 69 head = tail = 0; 70 for (int j = 1;j <= m + 1;++j) 71 { 72 while (head < tail && dp[i + 1][j] - pre[i][j - 1] >= dp[i + 1][q[tail - 1]] - pre[i][q[tail - 1] - 1]) 73 tail--; 74 q[tail++] = j; 75 while (head<tail && sum2[i][j-1] - sum2[i][q[head]-1]>k) 76 head++; 77 dp[i][j] = dp[i + 1][q[head]] + pre[i][j - 1] - pre[i][q[head]-1]; 78 } 79 head = tail = 0; 80 81 for (int j = m+1;j >= 1;--j) 82 { 83 while (head < tail&&dp[i + 1][j] - suf[i][j ] >= dp[i + 1][q[tail - 1]] - suf[i][q[tail - 1] ]) 84 tail--; 85 q[tail++] = j; 86 while (head<tail&&sum1[i][j] - sum1[i][q[head]]>k) 87 head++; 88 dp[i][j] =std::max(dp[i][j], dp[i + 1][q[head]] + suf[i][j] - suf[i][q[head]]); 89 } 90 } 91 int ans = 0; 92 for (int j = 1;j <= m + 1;++j) 93 ans = std::max(ans, dp[1][j]); 94 printf("%d ", ans); 95 } 96 return 0; 97 }