P1006 [NOIP2008 提高组] 传纸条

本文介绍: 在主函数开始的时候（还没执行任何语句）就出现了segmentation fa ul t！区别在于，这个地图不再是方阵，路线不能交叉，而且地图的大小可能大得多。但是思路都是相似的（或许你可以想想为什么路线不能交叉的影响不大）因为动态变量是储存在栈堆段上的，栈堆段的内存有限，太大会内存溢出。记得在算法书上看过，对于比较大的数组，最好把它设置为全局变量。还是动态规划，这题和我上一篇博客写的题差不多。

洛谷的题

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

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

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

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

解题思路就不赘述了

代码如下：

#include&lt;stdio.h&gt;
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", &amp;m, &amp;n);
    for(int i = 1 ; i &lt;= m; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &amp;map[i][j]);
    //开始动态规划
    for(int i = 1; i <= m + n - 2; i++)//i代表走了几步
    {
        for(int x1 = 1; x1 <= i + 1 &amp;&amp; x1 <= m; x1++)
        {
            int y1 = 2 + i - x1;
            if(y1 &gt; n) continue;
            for(int x2 = 1; x2 <= i + 1 &amp;&amp; x2 <= m; x2++)
            {
                if(x1 == x2)  continue;
                int y2 = 2 + i - x2;
                if(y2 &gt; 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 &gt; b) ? a : b;
    a = (a &gt; c) ? a : c;
    return (a > d) ? a : d;
}