BZOJ 3997
题意： 给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。
一开始觉得是上下界网络流。。范围太大了
这题是一个最小链覆盖问题，可以转化为最长反链覆盖。
考虑这里的反链，我们让$x$能到$y$看作偏序关系，然后对于$x,y$在同一反链当且仅当这两个点是右上、左下关系
那么设$dp(i,j)$为以$(i,j)$为左下角的矩形中的最长反链长。那么考虑转移
$$
dp(i,j)=\max(dp(i-1,j), dp(i,j+1), dp(i-1, j-1)+a_{i,j})
$$
前两个是继承关系，后一个是包含$(i,j)$的最长反链长，显然$(i,j)$和$(i-1, j-1)$在一个反链。
知识点
1、只向下/右：DP
2、二分图网络流问题：链、反链、最小点覆盖、最大独立集的转化
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
int T;
namespace flyinthesky {
const LL MAXN = 1000 + 5;
LL n, m, a[MAXN][MAXN], dp[MAXN][MAXN];
void clean() {
ms(dp, 0);
}
int solve() {
clean();
cin >> n >> m;
for (LL i = 1; i <= n; ++i)
for (LL j = 1; j <= m; ++j) scanf("%lld", &a[i][j]);
for (LL i = 1; i <= n; ++i) {
for (LL j = m; j >= 1; --j) {
dp[i][j] = max(dp[i - 1][j], max(dp[i][j + 1], dp[i - 1][j + 1] + a[i][j]));
}
}
cout << dp[n][1] << endl;
return 0;
}
}
int main() {
cin >> T;
while (T--) flyinthesky::solve();
return 0;
}
//
/*
*/
