CF1581 C.Portal【线性DP】

题目链接：codeforces 1581C

题解

定义 dp[i] 为前 列最小的花费。枚举时先枚举上下边，在对列 DP。因为第 列可能是边界，也可能在后面的过程中变成中间的部分，所以每次单独计算，而不算在 dp[i] 里面。

参考代码

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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 550;
int maze[N][N];
int tot0[N][N], tot1[N][N];
int dp[N];
int count0(int i, int j, int k) {
    return tot0[j][k] - tot0[i-1][k];
}
int count1(int i, int j, int k) {
    return tot1[j][k] - tot1[i-1][k];
}
int main() {
    int t; cin >> t;
    while (t--) {
        memset(tot0, 0, sizeof(tot0)); memset(tot1, 0, sizeof(tot1));
        int n, m; cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char c; cin >> c;
                maze[i][j] = c - '0';
                tot0[i][j] = tot0[i-1][j] + !maze[i][j];
                tot1[i][j] = tot1[i-1][j] + maze[i][j];
            }
        }
        int ans = 0x3f3f3f3f;
        for (int i = 1; i <= n; i++) {
            for (int j = i+4; j <= n; j++) {
                memset(dp, 0x3f, sizeof(dp));
                for (int k = 4; k <= m; k++) {
                    int cost = count0(i+1, j-1, k-3) + !maze[i][k-2] + !maze[i][k-1] + !maze[j][k-2] + !maze[j][k-1] + count1(i+1, j-1, k-2) + count1(i+1, j-1, k-1);
                    dp[k] = min(cost, dp[k-1] + count1(i+1, j-1, k-1) + !maze[i][k-1] + !maze[j][k-1]);
                    ans = min(ans, dp[k] + count0(i+1, j-1, k));
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}