网站推广渠道咨询,桂林两江四湖附近酒店,门户网站整改情况报告,网络整合营销理论摘花生 见另一篇文章#xff1a; Acwing数学与简单DP#xff08;二#xff09;
最低通行费 原题链接#xff1a;https://www.acwing.com/problem/content/1020/ 类似于上面的摘花生#xff0c;不过摘花生求的是集合的MAX#xff0c;最低通行费求的是集合的MIN。 但是 Acwing数学与简单DP二
最低通行费 原题链接https://www.acwing.com/problem/content/1020/ 类似于上面的摘花生不过摘花生求的是集合的MAX最低通行费求的是集合的MIN。 但是由于数组初始化为0。不能像摘花生一样简单的max()。 最后一步可能是从上方走来的也可能是从左方走来的。 对于除第一行和第一列的元素来说确实可以用min(上来左来)求较小值。 但对于处理边界元第一行和第一列时以第一行为例
从上方结果是0。通行费大于一min的值一定是0。
可不可以加一个特判呢
第一行的时候当前位置的值等于左来方式的值。第一列的时候当前位置的值等域上来方式的值。其余情况当前位置的值等于两种方式中的较小值。
思路比较清晰但写起来其实挺麻烦的。下面是另一种写法用一个新的表增加了空间但简化了写法。
状态表示f[i][j]左上角走到第i行第j列的最低通行费。集合属性MIN状态计算最后一步划分为从左来和从上来。
#includebits/stdc.husing namespace std;int N;
int w[110][110];
int dp[110][110];int main() {cin N;for (int i 1; i N; i) {for (int j 1; j N; j) {scanf(%d, w[i][j]);}}for (int i 1; i N; i) {for (int j 1; j N; j) {if (i 1 j 1)dp[i][j] w[i][j];else {dp[i][j] 1e9;if (i 1)dp[i][j] min(dp[i][j], dp[i - 1][j] w[i][j]);if (j 1)dp[i][j] min(dp[i][j], dp[i][j - 1] w[i][j]);}}}printf(%d\n, dp[N][N]);return 0;
}
上面代码的思路是特判左上角。 只有不在第一行的时候才可以从上面过来。 只有不再第一列的时候才可以从左边过来。
方格取数 原题链接https://www.acwing.com/problem/content/1029/ 摘花生中只走一次的情况
f[i][j]表示所有从(1,1)到(i,j)的路径的最大值。f[i][j]max(f[i-1][j],f[i][j-1])w[i][j]
走两次 f[i1][j1][i2][j2]表示所有从(1,1),(1,1)分别走到(i1,j1),(i2,j2)的路径的最大值。 如何处理“同一格子不能被重复选择”
只有在i1j1i2j2时两条路径的格子才可能重合
状态表示f[k][i1][i2]表示所有从(1,1),(1,1)分别走到(i,k-i1),(i2,k-i2)的路径的最大值。 k表示两条路线当前走过的格子的横纵坐标之和。
ki1j1i2j2
属性MAX 状态计算f[k][i1][i2]max(f[k - 1][i1 - 1][i2 - 1],f[k - 1][i1 - 1][i2],f[k - 1][i1][i2 - 1],f[k - 1][i1][i2])t
最后一步的第一条路线可以从上来、左来max(f[k - 1][i1-1][*],f[k - 1][i1][*])最后一步的第二条路线可以从上来、左来max(f[k - 1][*][i2-1],f[k - 1][*][i2])
#includebits/stdc.husing namespace std;int n;
int w[15][15];
int f[30][15][15];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 n; 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 i1 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[2 * n][n][n];return 0;
}
在while中判断结束的方法是,后位操作。
传纸条 原题链接https://www.acwing.com/problem/content/277/ 状态表示f[k][x1][x2]所有第一条从(1,1)走到(x1,k-x1)和第二条从(1,1)走到(x2,k-x2)的路线的最大好心程度之和。 属性MAX 状态计算
最后一步的两条路线分别有两种来法从上来、从左来。最后一步的位置可能相同t w[x1][k - x1]最后一步的位置可能不同t w[x1][k - x1] w[x2][k - x2]
#includebits/stdc.husing namespace std;int n, m;
int w[55][55];
int f[110][55][55];int main() {cin n m;for (int i 1; i n; i) {for (int j 1; j m; j) {cin w[i][j];}}for (int k 2; k m n; k) {for (int x1 max(1, k - m); x1 min(k - 1, n); x1) {for (int x2 max(1, k - m); x2 min(k - 1, n); x2) {int t w[x1][k - x1];if (x2 ! x1)t w[x2][k - x2];for (int a 0; a 1; a)for (int b 0; b 1; b)f[k][x1][x2] max(f[k][x1][x2], f[k - 1][x1 - a][x2 - b] t);}}}cout f[n m][n][n] endl;return 0;
}
传纸条在dp阶段的代码跟方格取数是一样的。 这是因为当两条路径相交时这个点加的值就是0w[i][j]。 如果选择让其中一条路径绕过这个点的话加值就是w[i][j-1]w[i][j]或w[i-1][j]w[i][j]。 因为是非负数所以绕路的情况一定优于有相交点的情况有相交点的路径一定不是最优解。 不论是在方格取数中还是在传纸条中最优解永远不会由两段相交的路径组成。
参考
https://www.acwing.com/solution/content/12389/
