这道题就是让你找出一个权值和最大的凸连通块~~（大水题）~~
首先，行数和格子数都可以作为 d p dp dp 的阶段，由于每次转移后选出的格子数是递增的，所以可以设计出以下状态表示
int f[25][250][20][20][2][2];//f[i][j][l][r][x][y] //前i行选择了j个格子，第i行选择第l到r个格子，左边界单调性为x(0为递增，1为递减)，右边界单调性为y()
状态转移方程：
初态：
F
[
i
,
0
,
0
,
0
,
1
,
0
]
=
0
F[i,0,0,0,1,0]=0
F[i,0,0,0,1,0]=0
目标：
m
a
x
F
[
i
,
K
,
l
,
r
,
x
,
y
]
max{F[i,K,l,r,x,y]}
maxF[i,K,l,r,x,y]
#includeusing namespace std; int n, m, k, res, ans; int i, j, l, r, x, y, ai, al, ar, ax, ay;//这里把循环变量都定义成全局变量是为了下面函数中调用的变量可以少一些，不容易出错 int a[25][25], b[25][25]; int ll[25][250][20][20][2][2], rr[25][250][20][20][2][2], xx[25][250][20][20][2][2], yy[25][250][20][20][2][2]; //用于记录每个状态的方案 int f[25][250][20][20][2][2];//f[i][j][l][r][x][y] //前i行选择了j个格子，第i行选择第l到r个格子，左边界单调性为x（0表示递增，1表示递减），右边界单调性为y void work(int val, int L, int R, int X, int Y) {//dp更新此时状态的答案并记录方案 if (val < f[i][j][l][r][x][y]) return ; f[i][j][l][r][x][y] = val; ll[i][j][l][r][x][y] = L; rr[i][j][l][r][x][y] = R; xx[i][j][l][r][x][y] = X; yy[i][j][l][r][x][y] = Y; } void wri(int i, int j, int l, int r, int x, int y) {//递归输出方案 if (j <= 0) return ; wri(i-1, j-(r-l+1), ll[i][j][l][r][x][y], rr[i][j][l][r][x][y], xx[i][j][l][r][x][y], yy[i][j][l][r][x][y]); for (j = l; j <= r; j++) printf("%d %dn", i, j); } int main() { // freopen("input.in","r",stdin); // freopen("output.out","w",stdout); scanf("%d%d%d", &n, &m, &k); memset(f, 0, sizeof(f)); for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) { scanf("%d", &a[i][j]); b[i][j] = b[i][j - 1] + a[i][j]; }//预处理一个前缀和数组 for (i = 1; i <= n; i++) for (j = 1; j <= k; j++) for (l = 1; l <= m; l++) for (r = l; r <= m; r++) { int t = r - l + 1; if (t > j) break; res = b[i][r] - b[i][l - 1]; x = 1; y = 0;//左边界列号递减，右边界列号递增（两边界都处于扩张状态） for (int p = l; p <= r; p++) for (int q = p; q <= r; q++) work(res+f[i-1][j-t][p][q][1][0], p, q, 1, 0); x = 1; y = 1;//左、右边界列号都递减（左边界扩张，右边界收缩） for (int p = l; p <= r; p++) for (int q = r; q <= m; q++) for (int v = 0; v < 2; v++) work(res+f[i-1][j-t][p][q][1][v], p, q, 1, v); x = 0; y = 0;//左、右边界列号都递增（左边界收缩，右边界扩张） for (int p = 1; p <= l; p++) for (int q = l; q <= r; q++) for (int u = 0; u < 2; u++) work(res+f[i-1][j-t][p][q][u][0], p, q, u, 0); x = 0; y = 1;//左边界列号递增，右边界列号递减（两个边界都处于收缩状态） for (int p = 1; p <= l; p++) for (int q = r; q <= m; q++) for (int u = 0; u < 2; u++) for (int v = 0; v < 2; v++) work(res+f[i-1][j-t][p][q][u][v], p, q, u, v); } for (i = 1; i <= n; i++) for (l = 1; l <= m; l++) for (r = l; r <= m; r++) for (x = 0; x < 2; x++) for (y = 0; y < 2; y++) if (ans < f[i][k][l][r][x][y]) {//找到最终的状态，然后记录下这个状态 ans = f[i][k][l][r][x][y]; ai = i; al = l; ar = r; ax = x; ay = y; } printf("Oil : %dn", ans); wri(ai, k, al, ar, ax, ay);//递归输出方案 return 0; }
over
