【BZOJ3997】[TJOI2015]组合数学 最长反链
数学 组合 最长
2023-09-11 14:15:27 时间
【BZOJ3997】[TJOI2015]组合数学
Description
给出一个网格图,其中某些格子有财宝,每次从左上角出发,只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形,假设每个格子中有好多财宝,而每一次经过一个格子至多只能捡走一块财宝,至少走多少次才能把财宝全部捡完。
Input
第一行为正整数T,代表数据组数。
每组数据第一行为正整数N,M代表网格图有N行M列,接下来N行每行M个非负整数,表示此格子中财宝数量,0代表没有
Output
输出一个整数,表示至少要走多少次。
Sample Input
1
3 3
0 1 5
5 0 0
1 0 0
3 3
0 1 5
5 0 0
1 0 0
Sample Output
10
HINT
N<=1000,M<=1000.每个格子中财宝数不超过10^6
题解:丧病结论题,拓扑图的最小链覆盖=最长反链。
于是n^2DP求出最长反链就行了。
#include <cstdio> #include <iostream> #include <cstring> using namespace std; int n,m; int v[1010][1010],f[1010][1010]; inline int rd() { int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f; } void work() { n=rd(),m=rd(); int i,j; for(i=1;i<=n;i++) for(j=1;j<=m;j++) v[i][j]=rd(); memset(f,0,sizeof(f)); for(j=m;j>=1;j--) { for(i=1;i<=n;i++) { f[i][j]=max(max(f[i-1][j],f[i][j+1]),f[i-1][j+1]+v[i][j]); } } printf("%d\n",f[n][1]); } int main() { int T=rd(); while(T--) work(); return 0; }
相关文章
- 【原创】开源Math.NET基础数学类库使用(09)相关数论函数使用
- 【数学建模绘图系列教程】二、折线图的绘制与优化
- 数学建模学习笔记(九)数据预处理
- 数学建模学习(17):图与网络模型之图详细讲解,最直白的话讲数据结构,内容偏多,建议先收藏
- POJ 3252 Round Numbers(组合数学)
- 27 组合数学-子集合问题
- 习题6.13 定义一个Student类,包含如下内容:成员变量:学号,姓名,性别,班干部否,数学,语文,外语 成员方法:输入,总分,平均分 编程实现这个类,并调用相应的方法输入数据,计算总分和平均分。
- Lesson15——NumPy 数学函数
- HDOJ--4869--Turn the pokers【组合数学+高速幂】
- 算法竞赛 | 组合数学之盒子和球
- 组合数学之Polya计数 TOJ1116 Let it Bead
- Python小白的数学建模课-06.固定费用问题
- 数学建模——运输问题(Python实现)