柯城建设局网站,海安市建设局网站,制作和淘宝商城一样网站,设计型网站自带优化算法提高课课堂笔记。 文章目录 摘花生题意思路代码 最低通行费题意思路代码 方格取数题意思路代码 摘花生
题目链接
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)#xff0c;从西北角进去#xff0c;东南角出来。
地里每个道…算法提高课课堂笔记。 文章目录 摘花生题意思路代码 最低通行费题意思路代码 方格取数题意思路代码 摘花生
题目链接
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)从西北角进去东南角出来。
地里每个道路的交叉点上都有种着一株花生苗上面有若干颗花生经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。 输入格式
第一行是一个整数T代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据从北向南依次描述每行花生苗的情况。每行数据有C个整数按从西向东的顺序描述了该行每株花生苗上的花生数目M。
输出格式
对每组输入数据输出一行内容为Hello Kitty能摘到得最多的花生颗数。
数据范围 1 ≤ T ≤ 100 , 1≤T≤100, 1≤T≤100, 1 ≤ R , C ≤ 100 , 1≤R,C≤100, 1≤R,C≤100, 0 ≤ M ≤ 1000 0≤M≤1000 0≤M≤1000
输入样例
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5输出样例
8
16题意
从左上角走到右下角求走过的交点最大权值和
思路
f[i][j]表示到达ij点权重的最大值
因为只能向右走或向下走所以到达ij点的方式一定是从左边的点向右走一步 / 从上面的点向下走一步
而左边的点权重最大值是f[i][j-1]上面的点权重最大值是f[i-1][j]从中取较大的加上自身权值即可
代码
#include bits/stdc.husing namespace std;const int N 110;int n, m;
int w[N][N];
int f[N][N];int main()
{int tt;cin tt;while (tt -- ){cin n m;for (int i 1; i n; i )for (int j 1; j m; j )cin w[i][j];for (int i 1; i n; i )for (int j 1; j m; j )f[i][j] max(f[i - 1][j], f[i][j - 1]) w[i][j];cout f[n][m] \n;}
}最低通行费
原题链接
一个商人穿过一个 N × N N×N N×N 的正方形的网格去参加一个非常重要的商务活动。
他要从网格的左上角进右下角出。
每穿越中间 1 个小方格都要花费 1 个单位时间。
商人必须在 ( 2 N − 1 ) (2N−1) (2N−1) 个单位时间穿越出去。
而在经过中间的每个小方格时都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用
注意不能对角穿越各个小方格即只能向上下左右四个方向移动且不能离开网格。
输入格式
第一行是一个整数表示正方形的宽度 N N N。
后面 N N N 行每行 N N N 个不大于 100 的正整数为网格上每个小方格的费用。
输出格式
输出一个整数表示至少需要的费用。
数据范围 1 ≤ N ≤ 100 1≤N≤100 1≤N≤100
输入样例
5
1 4 6 8 10
2 5 7 15 17
6 8 9 18 20
10 11 12 19 21
20 23 25 29 33输出样例
109样例解释
样例中最小值为 109 1 2 5 7 9 12 19 21 33 1091257912192133 1091257912192133。
题意
从左上角走到右下角不超过2n-1步求权重之和最小值
思路
和上一题一样都是左上角走到右下角
步数不超过2n-1翻译过来就是不走回头路
只是把最大值改成了最小值
代码
#include bits/stdc.husing namespace std;const int N 110, inf 0x3f3f3f3f;int n;
int w[N][N];
int f[N][N];int main()
{cin n;for (int i 1; i n; i )for (int j 1; j n; j )cin w[i][j];for (int i 1; i n; i )for (int j 1; j n; j )if (i 1 j 1) f[i][j] w[i][j];else{f[i][j] -inf;if (i 1) f[i][j] min(f[i][j], f[i - 1][j] w[i][j]);if (j 1) f[i][j] min(f[i][j], f[i][j - 1] w[i][j]);}cout f[n][n] \n;
}方格取数
题目链接
设有 N×N 的方格图我们在其中的某些方格中填入正整数而其它的方格中则放入数字0。如下图所示
某人从图中的左上角 A 出发可以向下行走也可以向右行走直到到达右下角的 B 点。
在走过的路上他可以取走方格中的数取走后的方格中将变为数字0。
此人从 A 点到 B 点共走了两次试找出两条这样的路径使得取得的数字和为最大。
输入格式
第一行为一个整数 N N N表示 N × N N×N N×N 的方格图。
接下来的每行有三个整数第一个为行号数第二个为列号数第三个为在该行、该列上所放的数。
行和列编号从 1 开始。
一行“0 0 0”表示结束。
输出格式
输出一个整数表示两条路径上取得的最大的和。
数据范围 N ≤ 10 N≤10 N≤10
输入样例
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0输出样例
67题意
矩阵中有数从左上角走到右下角走两次求权重最大值之和
思路
摘花生问题的扩展版走一次变成走两次
类比推广f[i1][j1][i2][j2]表示所有从1,1分别走到i1j1i2j2路径的最大值
如何处理同一个格子不被重复选择呢
因为从左上角走到右下角走的步数都是一样的所以i1 j1 i2 j2一定成立
所以我们可以将f[i1][j1][i2][j2]降维为f[k][i1][i2]k就是当前走过的步数
f[k][i1][i2]怎么计算呢
分为四种情况
第一条线路最后一步向下第二条线路最后一步向下f[k - 1][i1 - 1][i2 - 1]第一条线路最后一步向下第二条线路最后一步向右f[k - 1][i1 - 1][i2]第一条线路最后一步向右第二条线路最后一步向下f[k - 1][i1][i2 - 1]第一条线路最后一步向右第二条线路最后一步向右f[k - 1][i1][i2]
然后判断i1j1和i2j2是否重合重合只用加 w[i1][j1]不重合需要加w[i1][j1] w[i2][j2]
取最大值即可
代码
#include bits/stdc.husing namespace std;const int N 15;int n;
int w[N][N];
int f[N * 2][N][N];int main()
{cin n;int a, b, c;while (cin a b c, a || b || c) w[a][b] c;for (int k 2; k n * 2; k )for (int i1 1; i1 n; i1 )for (int i2 1; i2 n; i2 ){int j1 k - i1, j2 k - i2;if (j1 1 j1 n j2 1 j2 n){int t w[i1][j1];if (i1 ! i2) t w[i2][j2];int x f[k][i1][i2];x max(x, f[k - 1][i1 - 1][i2 - 1] t);x max(x, f[k - 1][i1 - 1][i2] t);x max(x, f[k - 1][i1][i2 - 1] t);x max(x, f[k - 1][i1][i2] t);}}cout f[n n][n][n] \n;
}
