AcWing 276. I-區域
題目
給出 n 行 m 列矩陣，和一個參數 k，求 k 個格子組成的凸聯通塊最大權值和。（凸連通塊就是形狀是凸性的）。n < 30, m <
分析
此處凸包定義不嚴謹，可以直接了解成連續的若幹行，每行的左端點列号先遞減、後遞增，右端點列号先遞增、後遞減。（這裡的遞增遞減都是不嚴格的）
那麼這樣就可以從每一行入手，考慮每行選取的起點和終點。
①： 狀态表示（經驗）
首先定義左右兩邊遞增狀态用 0 表示，遞減狀态用 1 表示。
- 集合： 表示所有選完前 i 行，且一共選了 j 個格子，第 i 行選取的左邊界是 L, 右邊界是 R，左邊界遞增遞減狀态是 x，右邊界遞增遞減狀态是 y 的連通塊的集合
- 屬性：表示集合中所有方案格子權值和最大值。
②： 狀态轉移
對于每行的選取，左右邊界的遞增遞減狀态都有要求，那麼如何在選取過程中滿足這種要求？設計一個狀态機：
也就是遞減狀态隻能由遞fdffd減推，而遞增狀态可以由遞減、遞增狀态推。這樣就滿足了題目要求（先遞減後遞增）。右邊界的自動機同理（先遞增後遞減）。
對于狀态 (x, y)：
假如為 (1, 0)，隻能由 (1, 0)轉移，即 (1, 0) --> (1, 0)
(1, 0), (1, 1) --> (1, 1)
(0, 0), (1, 0) --> (0, 0)
(0, 1), (1,1), (0, 0), (1, 0) —> (0, 1)
而同時考慮左右邊界 (L, R) 與上一行 (p, q) 的關系就有四種狀态：
-
當 ，則：
,其中：
-
當 ，則：
,其中：’
-
當 ，則：
,其中：
-
當 ，則：
,其中：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f;
const int N = 16;
int n, m, k;
int w[N][N]; // 每個點的權值
int dp[N][N * N][N][N][2][2];
struct State {
int i, j, l, r, x, y;
} f[N][N * N][N][N][2][2]; // 儲存狀态從什麼地方轉移過來
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &w[i][j]);
}
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= k; j++)
for (int l = 1; l <= m; l++)
for (int r = l; r <= m; r++) {
if (j < r - l + 1) continue;
// 左擴張，右擴張（1，0）
// 大括号為了變量名不幹擾
{
auto &vd = dp[i][j][l][r][1][0];
auto &vf = f[i][j][l][r][1][0];
for (int p = l; p <= r; p++)
for (int q = p; q <= r; q++) {
int val = dp[i - 1][j - (r - l + 1)][p][q][1][0];
if (vd < val) {
vd = val;
// 記錄路徑
vf = {i - 1, j - (r - l + 1), p, q, 1, 0};
}
}
for (int u = l; u <= r; u++) vd += w[i][u];
}
// 左擴張，右收縮（1，1）
{
auto &vd = dp[i][j][l][r][1][1];
auto &vf = f[i][j][l][r][1][1];
for (int p = l; p <= r; p++)
for (int q = r; q <= m; q++)
for (int y = 0; y < 2; y++) {
int val = dp[i - 1][j - (r - l + 1)][p][q][1][y];
if (vd < val) {
vd = val;
// 記錄路徑
vf = {i - 1, j - (r - l + 1), p, q, 1, y};
}
}
for (int u = l; u <= r; u++) vd += w[i][u];
}
// 左收縮，右擴張（0，0）
{
auto &vd = dp[i][j][l][r][0][0];
auto &vf = f[i][j][l][r][0][0];
for (int p = 1; p <= l; p++)
for (int q = l; q <= r; q++)
for (int x = 0; x < 2; x++) {
int val = dp[i - 1][j - (r - l + 1)][p][q][x][0];
if (vd < val) {
vd = val;
// 記錄路徑
vf = {i - 1, j - (r - l + 1), p, q, x, 0};
}
}
for (int u = l; u <= r; u++) vd += w[i][u];
}
// 左擴張，右擴張（0，1）
{
auto &vd = dp[i][j][l][r][0][1];
auto &vf = f[i][j][l][r][0][1];
for (int p = 1; p <= l; p++)
for (int q = r; q <= m; q++)
for (int x = 0; x < 2; x++)
for (int y = 0; y < 2; y++) {
int val = dp[i - 1][j - (r - l + 1)][p][q][x][y];
if (vd < val) {
vd = val;
// 記錄路徑
vf = {i - 1, j - (r - l + 1), p, q, x, y};
}
}
for (int u = l; u <= r; u++) vd += w[i][u];
}
}
int ans = 0;
State state;
for (int i = 1; i <= n; i++)
for (int l = 1; l <= m; l++)
for (int r = l; r <= m; r++)
for (int x = 0; x < 2; x++)
for (int y = 0; y < 2; y++) {
int val = dp[i][k][l][r][x][y];
if (ans < val) {
ans = val;
state = {i, k, l, r, x, y};
}
}
printf("oil : %d\n", ans);
while(state.j) {
for (int i = state.l; i <= state.r; i++)
printf("%d %d\n", state.i, i);
state = f[state.i][state.j][state.l][state.r][state.x][state.y];
}
return 0;
}