摘花生(数字三角形模型)
模型 数字 三角形
2023-09-11 14:20:29 时间
题目描述
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。
地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走,不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
![](https://img-blog.csdnimg.cn/img_convert/ab16689c581dd28ec3ce0c2c3f8463f1.gif)
输入格式
第一行是一个整数T,代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M。
输出格式
对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。
数据范围
1≤T≤100
1≤R,C≤100
0≤M≤1000
输入样例:
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例:
8
16
思考
对于每组数据进行处理,这是一道数字三角形模型衍生题
使用闫式分析法即可,f数组表示到达(i, j ) 时能够摘到的最多花生数量
有两种可能,分别是从左边来的,从上面来的,每次取每步方案的最大值,再加上本身的数量
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int n;
int a[N][N], f[N][N];
int main(){
scanf("%d", &n);
while(n--){
int r, c;
scanf("%d%d", &r, &c);
memset(a, 0, sizeof a);
memset(f, 0, sizeof f);
for(int i = 1; i <= r; i++)
for(int j = 1; j <= c; j++)
scanf("%d", &a[i][j]);
for(int i = 1; i <= r; i++)
for(int j = 1; j <= c; j++)
f[i][j] = max(f[i][j-1], f[i-1][j]) + a[i][j];
printf("%d\n", f[r][c]);
}
return 0;
}
相关文章
- 【华为云技术分享】HDC.Cloud | 以数字资产模型为核心驱动的一站式IoT数据分析实践
- 模型训练减少随机性
- 弹性盒子模型兼容性
- MVP模型
- NLP之TF-IDF:VSM向量空间模型(仅关键词组成的浮点数字向量)的简介、TF-IDF(VSM的常用的统计法)简介之详细攻略
- CV之FR之ME/LF:人脸识别中常用的模型评估指标/损失函数(Triplet Loss、Center Loss)简介、使用方法之详细攻略
- ML之PDP:基于titanic泰坦尼克是否获救二分类预测数据集利用PDP部分依赖图对RF随机森林实现模型可解释性案例
- ML之Xgboost:利用Xgboost模型(7f-CrVa+网格搜索调参)对数据集(比马印第安人糖尿病)进行二分类预测
- ML之SVM:利用SVM算法对手写数字图片识别数据集(PCA降维处理)进行预测并评估模型(两种算法)性能
- DL之DNN:利用DNN【784→50→100→10】算法对MNIST手写数字图片识别数据集进行预测、模型优化
- 主动配电网故障恢复的重构与孤岛划分统一模型研究【升级】(Matlab代码实现)
- 【控制模型】数字 PID 控制 — 增量式PID算法
- 数学建模学习(109):几行代码训练几十种机器学习模型
- 如何用CSharpOpenCv集成Yolov3的模型
- DIV+CSS两种盒子模型(W3C盒子与IE盒子)
- ML之FE:金融风控—基于预处理(PSI+标签编码+文本型抽数字+缺失值RF模型拟合填充)+多种筛选指标(PCA/IV值/Gini/熵/丰富度)利用CatBoost实现贷款违约二分类预测案例之详细攻略
- 【NLP】第 6 章 :微调预训练模型
- 898. 数字三角形(数字三角形模型)
- pytorch 24 把MMSegmentation的作为pytorch的语义分割模型库使用(已实现模型的训练与部署)