DDOSvoid's Blog

Luogu P3974 [TJOI2015]组合数学

发表于 更新于 分类于
本文字数： 985 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P3974

简要题意：给定一张 $n\times m$ 的网格图，从左上角出发，只能向右或者向下走，每个点有一个权值 $a_{i,j}$，每次经过一个点可以使权值减一，求至少走几次才能使所有点的权值为 $0$​

$n,m\le 1000,a_{i,j}\le 10^6$​

Solution

我们有结论，$DAG$ 上最小链覆盖等于最大独立集，这里我们可以看做每个点需要覆盖 $a_{i,j}$ 次，本质上是一样的

所以我们直接令 $f[i][j]$ 表示从 $(i,j)$ 到 $(1,n)$ 这个矩形的最大权独立集，然后做 $dp$ 即可

时间复杂度 $O(nm)$

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
#include <iostream>
#include <algorithm>
#define maxn 1010
#define ll long long
using namespace std;

int n, m, a[maxn][maxn];

ll f[maxn][maxn];

void work() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) cin >> a[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = m; j; --j) {
            f[i][j] = a[i][j];
            if (i > 1) f[i][j] = max(f[i][j], f[i - 1][j]);
            if (j < m) f[i][j] = max(f[i][j], f[i][j + 1]);
            if (i > 1 && j < m) f[i][j] = max(f[i][j], f[i - 1][j + 1] + a[i][j]);
        }
    cout << f[n][1] << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}