洛谷的题

网址：P1006 [NOIP2008 提高组] 传纸条 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

还是动态规划，这题和我上一篇博客写的题差不多

区别在于，这个地图不再是方阵，路线不能交叉，而且地图的大小可能大得多

但是思路都是相似的（或许你可以想想为什么路线不能交叉的影响不大）

解题思路就不赘述了

代码如下：

#include<stdio.h>
int getmax(int a, int b, int c, int d);
int m, n, map[51][51] = {0}, dp[51][51][51][51] = {0};int main(void)
{//输入scanf("%d%d", &m, &n);for(int i = 1 ; i <= m; i++)for(int j = 1; j <= n; j++)scanf("%d", &map[i][j]);//开始动态规划for(int i = 1; i <= m + n - 2; i++)//i代表走了几步{for(int x1 = 1; x1 <= i + 1 && x1 <= m; x1++){int y1 = 2 + i - x1;if(y1 > n) continue;for(int x2 = 1; x2 <= i + 1 && x2 <= m; x2++){if(x1 == x2)  continue;int y2 = 2 + i - x2;if(y2 > n)  continue;dp[x1][y1][x2][y2] = getmax(dp[x1 - 1][y1][x2 - 1][y2], dp[x1 - 1][y1][x2][y2 - 1], dp[x1][y1 - 1][x2 - 1][y2], dp[x1][y1 - 1][x2][y2 - 1]);dp[x1][y1][x2][y2] += map[x1][y1] + map[x2][y2];}}}//输出结果printf("%d", getmax(dp[m - 1][n][m][n - 1], dp[m][n - 1][m - 1][n], 0, 0));return 0;
}
int getmax(int a, int b, int c, int d)
{a = (a > b) ? a : b;a = (a > c) ? a : c;return (a > d) ? a : d;
}

但是在运行的时候，我遇到了前所未有的问题：

在主函数开始的时候（还没执行任何语句）就出现了segmentation fault！

为什么呢？

记得在算法书上看过，对于比较大的数组，最好把它设置为全局变量

因为动态变量是储存在栈堆段上的，栈堆段的内存有限，太大会内存溢出

小改了一下就解决了