神秘$dp$，不知道啥东西。
Solution
神仙换向$dp$。
首先发现$a[i][j]$和$a[i-1][j+1]$是不能同时取得，但是$a[i][j]$和$a[i-1][j]$及$a[i][j+1]$都是互通得的，根据联通性，我们可以将题目转化成从$(1,m)$走到$(n,1)$的最大非联通链（这样的链一定能覆盖$(1,1)$到$(n,m)$的路径），则其实是一个定理$DAG$的最小链赋盖$=$最大独立集，于是我们这样求出最大独立集即可。
Code
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
| #include <bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0;
bool flag = 0;
char c = getchar();
while (c < '0' || '9' < c) { if (c == '-') flag = 1; c = getchar(); }
while ('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if (flag) res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
if (res < 0) putchar('-'), res = -res;
if (res > 9) write(res / 10);
putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while (*s) putchar(*s++); }
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 1005, mod = 998244353;
int n, m, T;
int a[N][N];
LL f[N][N];
inline void work()
{
read(n, m);
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
read(a[i][j]);
memset(f, 0, sizeof(f));
for(int i = 1;i <= n;i ++)
for(int j = m;j >= 1;j --)
f[i][j] = max(max(f[i - 1][j], f[i][j + 1]),f[i - 1][j + 1] + a[i][j]);
write(f[n][1], '\n');
}
int main()
{
read(T);
while(T --) work();
return 0;
}
|