dp+优化
很明显可以用单调队列优化。
记录下自己犯的sb错误： 数组开小，sum没搞清。。。
#include<cstdio> #include<cstring> using namespace std; const int N = 110, M = 10010; int n, m, k, ans; int q[M]; int dp[N][M], sum[N][M], dis[N][M]; inline int max(int x, int y) { return x > y ? x : y; } inline int read() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int main() { //dp[i][j] = dp[i - 1][x] + sum[j] - sum[x - 1] //dp[i][j] = dp[i - 1][x] + sum[x] - sum[j - 1] while(scanf("%d%d%d", &n, &m, &k)) { memset(dp, 0, sizeof(dp)); ans = 0; if(n == 0 && m == 0 && k == 0) break; ++n; ++m; for(int i = 1; i <= n; ++i) for(int j = 2; j <= m; ++j) { int x; x = read(); sum[i][j] = sum[i][j - 1] + x; } for(int i = 1; i <= n; ++i) for(int j = 2; j <= m; ++j) { int x; x = read(); dis[i][j] = dis[i][j - 1] + x; } for(int i = 1; i <= n; ++i) { int l = 1, r = 0; q[++r] = 1; for(int j = 1; j <= m; ++j) { while(l <= r && dp[i - 1][j] - sum[i][j] > dp[i - 1][q[r]] - sum[i][q[r]]) --r; q[++r] = j; while(l <= r && dis[i][j] - dis[i][q[l]] > k) ++l; dp[i][j] = dp[i - 1][q[l]] + sum[i][j] - sum[i][q[l]]; } l = 1; r = 0; q[++r] = m; for(int j = m; j; --j) { while(l <= r && dp[i - 1][j] + sum[i][j] > dp[i - 1][q[r]] + sum[i][q[r]]) --r; q[++r] = j; while(l <= r && dis[i][q[l]] - dis[i][j] > k) ++l; dp[i][j] = max(dp[i][j], dp[i - 1][q[l]] + sum[i][q[l]] - sum[i][j]); if(i == n) ans = max(ans, dp[i][j]); } } printf("%d ", ans); } return 0; }