[TJOI2015]组合数学

各省省选 dp

题目链接：[TJOI2015]组合数学
参考资料：题解 P3974 【[TJOI2015]组合数学】

题目大意：

现有一个 $n*m$ 的网格，每个网格都有一定数量的宝藏，格点 $(i,j)$ 的宝藏数量为 $a[i][j]$ 。
从格点 $(1,1)$ 出发，只能往下或往右走，且每次经过一个格点只能取走该格点的一个宝藏，求最少要出发多少次才能取完所有宝藏。

解题思路：

这题突破点在于对网格的转化，一个只能往下或往右走的网格就相当于一个 DAG，那么求最少要走的次数就是求这个 DAG 的最小链覆盖。

Dilworth定理： DAG的最小链覆盖=最大点独立集

最小链覆盖： 指选出最少的链(可以重复)使得每个点都在至少一条链中

最大点独立集： 指最大的集合使集合中任意两点不可达

于是，问题就转化为求网格的最大点独立集。
已知，位于一个方格左下和右上的两个点是互不可达的，所以我们从右上向左下dp一边就行了。

注：我们将网格图转化为 DAG 是其实是将每一个权值作为一个点（如果一个点的权值为 5，那它就相当于 5 个点）。但是在dp时不需要将每一个点都考虑，只要加上网格中该节点的权值就好了。

状态转移方程：

（因为点 $(i,j)$ 的情况可以从它上方或右方的节点继承，所以还要加一个 $max(f[i-1][j],f[i][j+1]$

代码实现：

#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1000+7;
int T,n,m,a[N][N];
ll f[N][N];
int main(){
    cin>>T;
    while(T--){
        memset(f,0,sizeof(f));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        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]);
        printf("%lld\n",f[n][1]);
    }
    return 0;
}