题目描述
LYK进了一家古董店，它很想买其中的一幅画。但它带的钱不够买这幅画。
幸运的是，老板正在研究一个问题，他表示如果LYK能帮他解出这个问题的话，就把这幅画送给它。
老板有一个n*m的矩阵，他想找一个和最大的子矩阵，这个子矩阵可以由四个参数x,y,x2,y2(1<=x<=x2<=n,1<=y<=y2<=m)来表示，表示一个左上角为(x,y)，右下角为(x2,y2)的矩阵。
为了让游戏更加有趣，老板给了一个常数P，他想将原来这个矩阵中恰好一个数变为P，使得这个矩阵的最大的子矩阵尽可能大。
老板想知道这个最大值是多少。
你能帮帮LYK吗？
输入格式(puzzle.in)
第一行三个数n,m,P。
接下来n行，每行m个数ai,j描述整个矩阵。
输出格式(puzzle.out)
输出一个数表示答案。
输入样例
3 3 3
-100 3 3
3 -4 3
3 3 3
输出样例
20
样例解释
改变左上角那个数。
数据范围
对于20%的数据n,m<=10。
对于40%的数据n,m<=25。
对于60%的数据n,m<=50。
对于80%的数据n,m<=100。
对于100%的数据1<=n,m<=300，|P|,|ai,j|<=1000。
分析：先考虑最最基本的一个问题：给你一个序列，让你选一个子序列使得和最大.这道题可以很容易地用dp来解决，设f[i]表示前i个中的最大值，f[i] = max{f[i - 1] + a[i],a[i]}.推广到二维要怎么做呢？我们可以固定当前矩阵的上边界l和下边界r，压缩成一维，a[i] = sum[r] - sum[l - 1],然后进行dp就可以了.如果我们要让一个数变成P要怎么做呢？
当前状态转移不下去了，常用的办法是加一维，f[i][0]表示到前i列没有修改元素的最大和，f[i][1]类同，转移也很显然,如果当前的状态是f[i][0],那么之前肯定也没有修改，所以f[i][0] = max{f[i-1][0] + sum[i],sum[i]},如果当前的状态是f[i][1],那么如果之前修改过了，第i列肯定是不能改了，否则就必须改，所以f[i][1] = max{f[i-1][1] + sum[i],sum[i] - minn + p,f[i-1][0] + sum[i] - minn + p},minn为第i列最小的一个数，因为我们要改肯定是改最小的一个数嘛.固定好上下边界递推一下就可以了.
不过注意到必须要修改一个元素的限制，如果上下边界正好包含了整个矩形，那么答案只有可能从f[m][1]得到，其它情况下就可以从f[k][0/1]得到，因为我们可以在选取的子矩形里面改，也可以在外面改.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int inf = 0x7ffffff; int n, m, p, a[310][310], minn[310], b[310][310], d[310], f[310][310], ans = -inf; int main() { scanf("%d%d%d", &n, &m, &p); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); b[i][j] = a[i][j]; a[i][j] += a[i - 1][j]; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) minn[j] = b[i][j]; for (int j = i; j <= n; j++) { for (int k = 1; k <= m; k++) { minn[k] = min(minn[k], b[j][k]); d[k] = a[j][k] - a[i - 1][k]; } for (int k = 1; k <= m; k++) { f[k][0] = max(f[k - 1][0] + d[k], d[k]); f[k][1] = max(max(f[k - 1][1] + d[k], d[k] - minn[k] + p), f[k - 1][0] + d[k] - minn[k] + p); } if (i == 1 && j == n) ans = max(ans, f[m][1]); else for (int k = 1; k <= m; k++) ans = max(ans, max(f[k][0],f[k][1])); } } printf("%d ", ans); return 0; }