在哪里能建免费的网站,什么叫做电商平台,泰安房产网签最新消息,造价师注册管理系统擀面皮
有一块1x1的方形面团#xff08;不考虑面团的厚度#xff09;#xff0c;其口感值为0。擀面师傅要将其擀成一个N x M#xff08;纵向长N#xff0c;横向宽M#xff09;的面皮。师傅的擀面手法娴熟#xff0c;每次下手#xff0c;要么横向擀一下#xff08;使得…擀面皮
有一块1x1的方形面团不考虑面团的厚度其口感值为0。擀面师傅要将其擀成一个N x M纵向长N横向宽M的面皮。师傅的擀面手法娴熟每次下手要么横向擀一下使得横向长度增加1要么纵向擀一下使得纵向长度增加1。此外当面团皮的大小为a x b时往横向擀一下会使得面的口感值上升H_ab而往纵向擀一下则会使口感值上升V_ab。
现在请你来将1x1的面团擀成N x M面皮。显然从1x1的面团擀成N x M的面皮有多种不同的操作序列可以实现不同操作序列下得到的最终面皮口感值也可能是不同的。请问最终得到的N x M面皮口感值最高可为多少
输入描述
第一行两个整数NM表示要擀出来面皮的大小纵向长N横向宽M。
接下来有N行每行M个数。第a行第b列的数值H_ab表示当面皮大小为a x b时横向擀一下后面皮口感的上升值。
再接下来有N行每行M个数。第a行第b列的数值V_ab表示当面皮大小为a x b时纵向擀一下后面皮口感的上升值。
0 N, M 10000 H_ab, V_ab 1000
输出描述
输出最终得到的N x M面皮的最高的口感值。
示例1:
输入2 3
1 2 3
4 5 6
11 12 13
14 15 16
输出20 示例2:
输入3 3
1 0 2
2 0 2
2 2 0
0 2 2
1 2 1
2 1 2
输出7 提示
【示例1解释】
一共三种擀面方法
纵横横114520
横纵横112518
横横纵121316
【示例2解释】
最优擀面方法为:横(1) 纵(2) 纵(2) 横(2) 7
限制
时间1000ms
空间512MB
#include iostream
#include vectorint main() {int m, n;std::vectorstd::vectorint hSave;std::vectorstd::vectorint vSave;std::cinmn;int result[m][n];for (int i 0; i m; i) {std::vectorint temp(n);for (int j 0; j n; j) {std::cintemp[j];}hSave.push_back(temp);}for (int i 0; i m; i) {std::vectorint temp(n);for (int j 0; j n; j) {std::cintemp[j];}vSave.push_back(temp);}result[0][0] 0;for (int i 1; i m; i) {result[i][0] result[i - 1][0] vSave[i - 1][0];}for (int i 1; i n; i) {result[0][i] result[0][i - 1] hSave[0][i - 1];}for (int i 1; i m; i) {for (int j 1; j n; j) {result[i][j] std::max(result[i - 1][j] vSave[i - 1][j],result[i][j - 1] hSave[i][j - 1]);}}std::coutresult[m - 1][n - 1]std::endl;return 0;
}
解题算法动态规划
解题思路将擀面皮题转化为过门得分的思路假设是m*n个房间以m行n列的方式摆放在一起从左上角(0, 0)出发到右下角(m - 1, n - 1)且只能向右或向下需要经过m - 1 n - 1道门因为不能通向外界所以通向外界门的分数也就无用了如下图 可见纵向最下与横向最右均为无法使用的值所以我们只需要考虑可到达其他房间的门的数据。
我们知道到达每个房间时的得分与上方的房间加门和左侧房间加门相关取两者最大值作为当前房间的得分。最左侧的每间房得分只与上方有关顶层的每间房得分只与左侧有关所以我们可以先得到顶层和最左侧的房间得分。
假设我们的表格名为result横向数据用 h 表示纵向数据用 v 表示我们的转移方程如下 因为顶层与最左侧已经填充完毕所以不用担心下标为负值的情况。
