中国做国际期货最大的网站,wordpress 文章访问次数,动漫制作专业就业,软件开发 上海Acwing 276. I-区域
题意#xff1a;
在 NM 的矩阵中#xff0c;每个格子有一个权值#xff0c;要求寻找一个包含 K 个格子的凸连通块#xff08;连通块中间没有空缺#xff0c;并且轮廓是凸的#xff09;#xff0c;使这个连通块中的格子的权值和最大。 注意#xf…Acwing 276. I-区域
题意
在 N×M 的矩阵中每个格子有一个权值要求寻找一个包含 K 个格子的凸连通块连通块中间没有空缺并且轮廓是凸的使这个连通块中的格子的权值和最大。 注意凸连通块是指连续的若干行每行的左端点列号先递减、后递增右端点列号先递增、后递减。
求出这个最大的权值和并给出连通块的具体方案输出任意一种方案即可。 1≤N,M≤15, 0≤K≤N×M
题解
很简单但是又很麻烦 我们考虑每一行都需要根据上一行的情况来因为我们要考虑这个凸连通块的问题 dp[i][j][l][r][x(0/1)][y(0/1)]:表示前i行选择了j个格子其中第i行选择了第l行到第r行左端点x为单调伸长/单调伸短右端点x为单调伸长/单调伸短的最大权值
进阶指南中的状态转移 注书中的单调伸长与我上面讲的不同书中定义左端点的单调伸长为1右端点的单调伸长为0 答案最后还要输出格子位置要记录路径信息 细节挺好详细看看代码
代码
#include cstdio
#include iostream
#include cstring
using namespace std;
const int N 16;struct S{int i, j, l, r, x, y;
}pre[N][N * N][N][N][2][2], t;int n, m, k, a[N][N], f[N][N * N][N][N][2][2];
int ans 0;int inline cost(int i, int l, int r){return a[i][r] - a[i][l - 1];
}void print(S x){if(x.j 0) return;print(pre[x.i][x.j][x.l][x.r][x.x][x.y]);for(int i x.l; i x.r; i) printf(%d %d\n, x.i, i);
}int main(){memset(f, 0xcf, sizeof f);//初始化为负无穷 //coutf[0][0][0][0][0][0]endl;scanf(%d%d%d, n, m, k);for(int r 0; r n; r) {for(int i 1; i m; i){for(int j i; j m; j)f[r][0][i][j][0][0] 0;}}for(int i 1; i n; i)for(int j 1; j m; j)scanf(%d, a[i][j]), a[i][j] a[i][j - 1];for(int i 1; i n; i){for(int j 1; j k; j){for(int l 1; l m; l){for(int r l; r m; r){if(j r - l 1) continue;//x 0, y 0;for(int l1 l; l1 r; l1){for(int r1 l1; r1 r; r1){int v f[i][j][l][r][0][0], val f[i - 1][j - (r - l 1)][l1][r1][0][0] cost(i, l, r);if(v val) {v val, pre[i][j][l][r][0][0] (S){i - 1, j - (r - l 1), l1, r1, 0, 0};}}}//x 0, y 1;for(int l1 l; l1 r; l1){for(int r1 r; r1 m; r1){for(int y1 0; y1 2; y1) {int v f[i][j][l][r][0][1], val f[i - 1][j - (r - l 1)][l1][r1][0][y1] cost(i, l, r);if(v val) {v val, pre[i][j][l][r][0][1] (S){i - 1, j - (r - l 1), l1, r1, 0, y1};}}}}// x 1, y 0;for(int l1 1; l1 l; l1){for(int r1 l; r1 r; r1){for(int x1 0; x1 2; x1) {int v f[i][j][l][r][1][0], val f[i - 1][j - (r - l 1)][l1][r1][x1][0] cost(i, l, r);if(v val) {v val, pre[i][j][l][r][1][0] (S){i - 1, j - (r - l 1), l1, r1, x1, 0};} }}}// x 1, y 1;for(int l1 1; l1 l; l1){for(int r1 r; r1 m; r1){for(int x1 0; x1 2; x1) {for(int y1 0; y1 2; y1) {int v f[i][j][l][r][1][1], val f[i - 1][j - (r - l 1)][l1][r1][x1][y1] cost(i, l, r);if(v val) {v val, pre[i][j][l][r][1][1] (S){i - 1, j - (r - l 1), l1, r1, x1, y1};}}}}}if(j k){for(int x 0; x 2; x) {for(int y 0; y 2; y) {if(ans f[i][j][l][r][x][y]) {ans f[i][j][l][r][x][y], t (S){i, j, l, r, x, y};}}}}}}}}printf(Oil : %d\n, ans);print(t);return 0;
}
