You are given a matrix f with 4 rows and n columns. Each element of the matrix is either an asterisk (*) or a dot (.).
You may perform the following operation arbitrary number of times: choose a square submatrix of f with size k × k (where 1 ≤ k ≤ 4) and replace each element of the chosen submatrix with a dot. Choosing a submatrix of size k × k costs ak coins.
What is the minimum number of coins you have to pay to replace all asterisks with dots?
Input
The first line contains one integer n (4 ≤ n ≤ 1000) — the number of columns in f.
The second line contains 4 integers a1, a2, a3, a4 (1 ≤ ai ≤ 1000) — the cost to replace the square submatrix of size 1 × 1, 2 × 2, 3 × 3or 4 × 4, respectively.
Then four lines follow, each containing n characters and denoting a row of matrix f. Each character is either a dot or an asterisk.
Output
Print one integer — the minimum number of coins to replace all asterisks with dots.
Examples
|
1 2 3 4 5 6 |
4 1 10 8 20 ***. ***. ***. ...* |
|
1 |
9 |
|
1 2 3 4 5 6 |
7 2 1 8 2 .***... .***..* .***... ....*.. |
|
1 |
3 |
|
1 2 3 4 5 6 |
4 10 10 1 10 ***. *..* *..* .*** |
|
1 |
2 |
Note
In the first example you can spend 8 coins to replace the submatrix 3 × 3 in the top-left corner, and 1 coin to replace the 1 × 1 submatrix in the bottom-right corner.
In the second example the best option is to replace the 4 × 4 submatrix containing columns 2 – 5, and the 2 × 2 submatrix consisting of rows 2 – 3 and columns 6 – 7.
In the third example you can select submatrix 3 × 3 in the top-left corner and then submatrix 3 × 3 consisting of rows 2 – 4 and columns 2 – 4.
题意简述
有一个 $4\times n$ 的矩阵，矩阵中有一些点需要清除。有四种清除方式——第 $i$ 种为把一个 $i\times i$ 的子矩阵里的点都清除。每种清除方式有不同的代价。求将所有该清除的点都清除需要花费的最小代价。
分析
一开始想的是状态 $f(i, \cdots )$ 表示所有子矩阵都摆在前 $i$ 列，再满足一些其他条件时最小代价，之所以是都摆在前 $i$ 列是为了方便满足后效性。然后发现状态怎么设计都找不到较优的解决方案。
考虑将第一维放宽一些，用 $f(i, \cdots )$ 表示所有子矩阵的左上角都在前 $i$ 列，再满足其他一些条件的最小代价。这样设计状态不方便满足后效性，因为有一些不在前 $i$ 列的点也被清除了，对我们在之后摆放矩阵的方式会有一定影响。可以考虑如何消除后效性，也就是如何增加一些状态来记录后面的点是否被清除。
显然，当所有子矩阵的左上角都在前 $i$ 列时，超出前 $i$ 列最多覆盖 3 列，因此可以设计状态 $f(i, k_0, k_1, k_2, k_3)$ 表示所有子矩阵的左上角都在前 $i$ 列，已经清除前 $i$ 列所有点，且四行各多向右覆盖 $k_0, k_1, k_2, k_3$ 个格子的最小代价。
转移就只要枚举所有在这一列上摆放格子的方案即可。
（通过预处理可以有效地提升效率并使代码更有条理）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#include <cstdio> #include <cstring> #include <algorithm> using std::max; using std::min; struct options { int cost, k[4]; }; options opt[200], enums[1000]; int n, cost[5], tot, cnt; int dp[1005][5][5][5][5]; char str[4][1005]; void dfs(int now, int lim, int *arr, int money = 0) { if (now == 0) { opt[++tot] = (options) {money, arr[0], arr[1], arr[2], arr[3]}; // printf("%d : %d %d %d %d\n", money, arr[0], arr[1], arr[2], arr[3]); return; } if (lim < 0) lim = 0; int tmp[4] = {arr[0], arr[1], arr[2], arr[3]}; for (int i = 0; i <= now; ++i) { if (i > 0 && i < lim) continue; for (int j = 4 - now; j < 4 - now + i; ++j) tmp[j] = max(tmp[j], i); dfs(now - 1, max(lim - 1, i), tmp, money + cost[i]); memcpy(tmp, arr, sizeof tmp); } } void dfs2(int now, int *arr) { if (now == 0) { enums[++cnt] = (options) {0, arr[0], arr[1], arr[2], arr[3]}; return; } for (int i = 0; i < 5; ++i) { arr[now - 1] = i; dfs2(now - 1, arr); } } int main() { scanf("%d", &n); for (int i = 1; i <= 4; ++i) scanf("%d", &cost[i]); int tmp[4] = {0, 0, 0, 0}; dfs(4, 0, tmp); dfs2(4, tmp); for (int i = 0; i < 4; ++i) scanf("%s", str[i]); memset(dp, 63, sizeof dp); dp[0][0][0][0][0] = 0; for (int i = 0; i < n; ++i) { for (int j = 1; j <= cnt; ++j) { int k0 = enums[j].k[0]; int k1 = enums[j].k[1]; int k2 = enums[j].k[2]; int k3 = enums[j].k[3]; if (dp[i][k0][k1][k2][k3] > 1e8) continue; // printf("dp[%d][%d][%d][%d][%d] = %d\n", i, k0, k1, k2, k3, dp[i][k0][k1][k2][k3]); for (int l = 1; l <= tot; ++l) { int v0 = max(k0, opt[l].k[0]); int v1 = max(k1, opt[l].k[1]); int v2 = max(k2, opt[l].k[2]); int v3 = max(k3, opt[l].k[3]); int v = opt[l].cost; if (v0 == 0 && str[0][i] == '*') continue; if (v1 == 0 && str[1][i] == '*') continue; if (v2 == 0 && str[2][i] == '*') continue; if (v3 == 0 && str[3][i] == '*') continue; if (--v0 < 0) v0 = 0; if (--v1 < 0) v1 = 0; if (--v2 < 0) v2 = 0; if (--v3 < 0) v3 = 0; dp[i + 1][v0][v1][v2][v3] = min(dp[i + 1][v0][v1][v2][v3], dp[i][k0][k1][k2][k3] + v); } } } int ans = 1071026353; for (int j = 1; j <= cnt; ++j) { int k0 = enums[j].k[0]; int k1 = enums[j].k[1]; int k2 = enums[j].k[2]; int k3 = enums[j].k[3]; ans = min(ans, dp[n][k0][k1][k2][k3]); } printf("%d\n", ans); return 0; } |