搜索网站入口,淮南医院网站建设,网站设计鉴赏,创建全国文明城市我们在行动绘画母题#xff1a;数字三角形
集合#xff1a;f[i][j]表示所有从起点走到 ( i , j ) (i,j) (i,j)的路径 属性#xff1a;f[i][j]存的数是集合中所有路径和的最大值
状态计算#xff1a;对于每一条从起点到 ( i , j ) (i,j) (i,j) 的路径#xff0c;其要么是从左上方来的…母题数字三角形
集合f[i][j]表示所有从起点走到 ( i , j ) (i,j) (i,j)的路径 属性f[i][j]存的数是集合中所有路径和的最大值
状态计算对于每一条从起点到 ( i , j ) (i,j) (i,j) 的路径其要么是从左上方来的要么是从右上方来的。
左上方f[i][j] f[i-1][j-1] a[i][j] (a[i][j]为终点的值) 右上方f[i][j] f[i-1][j] a[i][j] 两者再取max即可。
#include bits/stdc.husing namespace std;const int N 510, INF 0x3f3f3f3f;
int f[N][N], a[N][N];int main()
{int n;cin n;for (int i 1; i n; i) for (int j 1; j i; j) cin a[i][j];for (int i 1; i n; i) for (int j 0; j i 1; j) f[i][j] -INF;f[1][1] a[1][1];//顶点就是那个数for (int i 2; i n; i)//从第二行开始状态计算for (int j 1; j i; j)f[i][j] max(f[i-1][j-1] a[i][j], f[i-1][j] a[i][j]);int ans -INF;for (int i 1; i n; i) ans max(ans, f[n][i]);//f[n][i]表示从起点走到最后一行的第i个数的路径最大值这i个数之间彼此还要再比出一个最大值cout ans; return 0;
}需要注意的是初始化由于整数有可能是负数且属性是 M a x \rm Max Max所以仅全局的默认初始化为 0 0 0 是不行的需要初始化为负无穷。
此外等腰三角形的左右两条边分别不能从左上和右上递推因此初始化时需要考虑边界 j j j 从 0 0 0 开始到 i 1 i1 i1 结束但 i i i 无需更改因为只是左右的边界问题。
为了避免边界问题本题也可以采取由下到上的 d p dp dp 方式。 从下到上的话所有的点包括左右两条边上的点都一定可以从左下和右下两个方向递推因此不需要考虑边界也无需初始化。状态转移方程为f[i][j] max(f[i1][j1] a[i][j], f[i1][j] a[i][j])
#include bits/stdc.husing namespace std;const int N 510, INF 0x3f3f3f3f;
int f[N][N], a[N][N];int main()
{int n;cin n;for (int i 1; i n; i) for (int j 1; j i; j) cin a[i][j];for (int i 1; i n; i) f[n][i] a[n][i];//初始化最后一行for (int i n-1; i 1; i--)//从倒数第二行往上计算状态for (int j 1; j i; j)//与左右无关不影响顺序f[i][j] max(f[i1][j1] a[i][j], f[i1][j] a[i][j]);cout f[1][1];//最后枚举到顶点(1,1),f[1][1]即为最大值return 0;
}子题1摘花生
和数字三角形的状态转移方程基本一致。
#include cstdio
#include algorithmconst int N 110;int w[N][N], f[N][N];int main()
{int T;scanf(%d, T);while (T--) {int n, m;scanf(%d%d, n, m);for (int i 1; i n; i) {for (int j 1; j m; j) {scanf(%d, w[i][j]);}}for (int i 1; i n; i) {for (int j 1; j m; j) {f[i][j] std::max(f[i-1][j], f[i][j-1]) w[i][j];}}printf(%d\n, f[n][m]);}return 0;
}子题2最低通行费
#include cstdio
#include cstring
#include algorithmconst int N 110;
int w[N][N], f[N][N];int main()
{int n;scanf(%d, n);for (int i 1; i n; i) {for (int j 1; j n; j) {scanf(%d, w[i][j]);}}memset(f, 0x3f, sizeof f);//摘花生的属性是max因此f无需初始化初始值为0可以在状态计算中自动覆盖但本题的属性为minf需初始化为∞f[1][1] w[1][1];for (int i 1; i n; i) {for (int j 1; j n; j) {if (j 1) f[i][j] std::min(f[i][j], f[i-1][j] w[i][j]);else if (i 1) f[i][j] std::min(f[i][j], f[i][j-1] w[i][j]);//最左边一列和最上面一行的状态转移分别只能从上面和左面转移else {f[i][j] std::min(f[i][j-1], f[i-1][j]) w[i][j];}}}printf(%d, f[n][n]);return 0;
}也可以这么写:
#include cstdio
#include cstring
#include algorithmconst int N 110;
int w[N][N], f[N][N];int main()
{int n;scanf(%d, n);for (int i 1; i n; i) {for (int j 1; j n; j) {scanf(%d, w[i][j]);}}memset(f, 0x3f, sizeof f);f[1][1] w[1][1];for (int i 1; i n; i) {for (int j 1; j n; j) {f[i][j] std::min(f[i][j], f[i-1][j] w[i][j]);f[i][j] std::min(f[i][j], f[i][j-1] w[i][j]);}}printf(%d, f[n][n]);return 0;
}m i n \rm min min 的括号里写f[i][j]是为了不特判起点f[1][1]。保险起见建议特判一下起点每次仔细思考边界和属性的关系。
子题3方格取数
误区避雷为什么不能分开两次走贪心 第一次走到 ( n , n ) (n, n) (n,n) 求出最大值并记录路径令路径上点收益为 0 0 0 后再走一次。 第一次走为局部最优并且也对第二次走造成了影响第二次走是在第一次影响下所能走的局部最优不具备“无后效性”因此分开两次走并不是全局最优解。
换言之第一次走的时候有可能有好几条路径都是第一次的解而你分开走只能选择其中的一条。很不幸的是第一次走过的地方会被重置成 0 0 0 而你不确定的是第一次同样是最优解而未被你选择的情况下第二次的值会不会比你已经得出的答案要大。
因此我们两条路同时走从 ( 1 , 1 ) (1,1) (1,1) 走到 ( n , n ) (n,n) (n,n)。用 f [ i 1 ] [ j 1 ] [ i 2 ] [ j 2 ] f[i_1][j_1][i_2][j_2] f[i1][j1][i2][j2] 表示从 ( 1 , 1 ) (1,1) (1,1) ( 1 , 1 ) (1,1) (1,1) 走到 ( i 1 , j 1 ) (i_1,j_1) (i1,j1) ( i 2 , j 2 ) (i_2,j_2) (i2,j2) 能取得的最大的数字和。
由于两条路同时走有 i 1 j 1 i 2 j 2 i_1 j_1 i_2 j_2 i1j1i2j2。因此四维的 d p dp dp 可以被优化到三维。 令 k i 1 j 1 k i_1 j_1 ki1j1 f [ k ] [ i 1 ] [ i 2 ] f[k][i_1][i_2] f[k][i1][i2] 就表示 f [ i 1 ] [ j 1 ] [ i 2 ] [ j 2 ] f[i_1][j_1][i_2][j_2] f[i1][j1][i2][j2]。
状态计算 集合划分看最后一步的操作。由于是分别从 ( 1 , 1 ) (1,1) (1,1) ( 1 , 1 ) (1,1) (1,1) 走到 ( i 1 , j 1 ) (i_1,j_1) (i1,j1) ( i 2 , j 2 ) (i_2,j_2) (i2,j2)而每条路的最后一步都可能是向右或向下因此总共可以将集合分为 4 4 4 个子集。 ① 最后一步分别是下、下 f [ k − 1 ] [ i 1 − 1 ] [ i 2 − 1 ] f[k-1][i_1 - 1][i_2 - 1] f[k−1][i1−1][i2−1] ② 最后一步分别是右、下 f [ k − 1 ] [ i 1 ] [ i 2 − 1 ] f[k-1][i_1][i_2 - 1] f[k−1][i1][i2−1] ③ 最后一步分别是下、右 f [ k − 1 ] [ i 1 − 1 ] [ i 2 ] f[k-1][i_1 - 1][i_2] f[k−1][i1−1][i2] ④ 最后一步分别是右、右 f [ k − 1 ] [ i 1 ] [ i 2 ] f[k-1][i_1][i_2] f[k−1][i1][i2]
当 i 1 i 2 i_1 i_2 i1i2 且 j 1 j 2 j_1 j_2 j1j2 的情况下两点重合只需加上 w [ i 1 ] [ j 1 ] w[i_1][j_1] w[i1][j1]否则的话还需加上 w [ i 2 ] [ j 2 ] w[i_2][j_2] w[i2][j2]。
#include cstdio
#include algorithmconst int N 15;
int w[N][N], f[N * 2][N][N];int main()
{int n;scanf(%d, n);int a, b, c;while (scanf(%d%d%d, a, b, c) ! EOF, a || b || c) w[a][b] c;for (int k 2; k n * 2; k) {//起始时(1,1), k 2for (int i1 1; i1 k; i1) {for (int i2 1; i2 k; i2) {int j1 k - i1, j2 k - i2;int t w[i1][j1];if (i1 ! i2) t w[i2][j2];int x f[k][i1][i2];x std::max(x, f[k - 1][i1 - 1][i2 - 1] t);x std::max(x, f[k - 1][i1 - 1][i2] t);x std::max(x, f[k - 1][i1][i2 - 1] t);x std::max(x, f[k - 1][i1][i2] t);}}}printf(%d, f[n * 2][n][n]);return 0;
}需要注意的一点是这里 i 1 i_1 i1 和 i 2 i_2 i2 的范围不可直接写 i1 n、i2 n这样在 k k k 较小的时候 j 1 j_1 j1、 j 2 j_2 j2 就会小于 0 0 0不符合题意。建议书写i1 n i1 k、i2 n i2 k包含了其固有的范围和题目要求的范围。
子题4传纸条
首先需要明确的是从右下角回传可以等价为从左上角传两次。
如果两个点相交这个点的值只能加一次然而我们肯定能找到一条绕过这个点走到下个点的路径这条路径一定是大于之前相交路径的。
数学表达就是两条路径在一个点那么在这个点加的值就是 0 g [ i , j ] 0g[i,j] 0g[i,j], 但是我们可以让其中一条路径绕过这个点再走到这个点的下一个点 那么加的值应该是 g [ i , j − 1 ] g [ i , j ] g[i,j-1] g[i,j] g[i,j−1]g[i,j]。
因为是非负数所以我们可以找到一条大于等于之前有相交点的路径那么这个有相交点的一定不是最优解即便这条路径是最优解也有另一条最优解和这个路径和一样但是我们只需要输出路径和就可以了最优解路径有可能是有相交点的但是也有另一个最优解没有相交点那么我们输出的路径和肯定可以是一条没有相交点的最优解。
以上就证明了本题中“不允许走同一个点”的要求没用最优解的情况与方格取数完全一致。
#include cstdio
#include algorithmconst int N 55;
int w[N][N], f[N 1][N][N];int main()
{int m, n;scanf(%d%d, m, n);for (int i 1; i m; i) {for (int j 1; j n; j) {scanf(%d, w[i][j]);}}for (int k 2; k n m; k) {for (int i1 1; i1 m i1 k; i1) {for (int i2 1; i2 m i2 k; i2) {int j1 k - i1, j2 k - i2;int x f[k][i1][i2];int t w[i1][j1];if (i1 ! i2) t w[i2][j2];x std::max(x, f[k - 1][i1 - 1][i2 - 1] t);x std::max(x, f[k - 1][i1 - 1][i2] t);x std::max(x, f[k - 1][i1][i2 - 1] t);x std::max(x, f[k - 1][i1][i2] t);}}}printf(%d, f[n m][m][m]);return 0;
}
