题目描述
为了提高智商,ZJY开始学习组合数学。某一天她解决了这样一个问题:给一个网格图,其中某些格子有财宝。每次从左上角出发,只能往右或下走。问至少要走几次才可能把财宝全捡完。
但是她还不知足,想到了这个问题的一个变形:假设每个格子中有好多块财宝,而每一次经过一个格子至多只能捡走一块财宝,其他条件不变,至少要走几次才可能把财宝全捡完?
这次她不会做了,你能帮帮她吗?
输入输出格式
输入格式:
第一行为一个正整数t,表示数据组数
每组数据的第一行是两个正整数n和m,表示这个网格图有n行m列。
接下来n行,每行m个非负整数,表示这个格子中的财宝数量(0表示没有财宝)。
输出格式:
对于每组数据,输出一个整数,表示至少走的次数。
输入输出样例
输入样例#1:1 3 3 0 1 5 5 0 0 1 0 0输出样例#1:
10
说明
数据范围
对于30%的数据,n≤5.m≤5,每个格子中的财宝数不超过5块。
对于50%的数据,n≤100,m≤100,每个格子中的财宝数不超过1000块
对于100%的数据,n≤1000,m≤1000,每个格子中的财宝不超过10^6块
解析:
这是天津市2015年的省选题(天津好像离北京很近~~~)于是乎我就做了这道题。。。
题目的意思就是用最少的链覆盖住整个图,自然而然(看过题解后)就想到了最小链覆盖;
而根据著名的(反正我是没听过)的Dilworth定理,DAG最小链覆盖的条数就等于最大点独立集/最长反链的元素个数;;;
所谓de反链就是去找一些点,其中找两个点,使其直接间接均不可达;而反链中元素最多的就是最长反链了。
所以这个题的本质上是去找这个图的最长反链。
接下来就到了我们有趣的dynamic programming环节辣;;;
由题目可知,只能从左往右,从上往下走,所以这个题的反链一定是由右上到左下的。
而从上面和右面均能形成链,所以直接它直接就可能是这个点的最长反链;
从右上走到左下是不可能的,所以我们要把右上的点加上这个点的值才可能是最长反链;
而我们要求的是最长反链,但这几个部分显然是不能够同时取的,所以要选这三个的最大值
状态转移方程就很容易写出了:
f[i][j]=max(f[i-1][j+1]+a[i][j],max(f[i-1][j],f[i][j+1]));
这里还要注意的一点就是循环变量,i是从1-〉n递增的,j是从m-〉1递减的,原因很简单,就是要满足最长反链从左下不可能到达右上的性质;
下面上代码:
#include<iostream> #include<cstdio>//getchar要引cstdio using namespace std; int t,n,m; long long a[1005][1005],f[1005][1005];//要开大!洛谷上本题有5个极限数据,不开就会RE得很惨~ int read()//读入优化 { int f=1,x=0; char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } int main() { t=read(); for(int s=1;s<=t;s++) { n=read(); m=read(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { a[i][j]=read(); f[i][j]=0; } }
//dp for(int i=1;i<=n;i++) { for(int j=m;j>=1;j--) { f[i][j]=max(f[i-1][j+1]+a[i][j],max(f[i-1][j],f[i][j+1])); } } cout<<f[n][1]<<endl;//千万不要忘记输出回车。。。我爆了5次零。。。 } }