soj1767.传纸条

这道题目想了一会儿觉得不知道如何下手，上网看了下资料，原来这道是一道非常经典的题目。

设 f [ k ][ i ][ j ] 表示第 k 步，第 1 条路径走到第 i 行，第 2 条路径走到第 j 行的最大权值和。
      状态转移方程：
      f [ k ][ i ][ j ] = max { f [ k - 1 ][ i - 1 ][ j ], f [ k - 1 ][ i ][ j - 1 ], f [ k - 1 ][ i ][ j ], f [ k - 1 ][ i - 1 ][ j - 1 ] } + map[ i ][ k - i ] + map[ j ][ k - j ]
      ( 2 <= k <= m + n, 1 <= i, j <= min { m, k - 1 }, i != j )

#include <iostream>

#include <algorithm>

#include <memory.h>

using namespace std;

int paper[110][52][52];

int map[52][52];

int Max(int a,int b,int c,int d)

{

	return max(max(a,b),max(c,d));

}

int main()

{

    int m, n;

	while (cin >> m >> n)

    {

		memset(paper,0,sizeof(paper));

		int i,j,k;

        for (i = 1; i <= m; i ++)

        {

            for (j = 1; j <= n; j ++)

            {

                cin >> map[i][j];

            }

        }

		memset(paper, 0, sizeof(paper));

		for (k = 1; k <= m + n; k ++)

        {

            for (i = 1; i <= min(m,k-1); i ++)

            {

                for (int j = 1; j <= min(m,k-1); j ++)

                {

                    if (k != m + n && i == j)

						continue;

					else

					{

						paper[k][i][j] = Max(paper[k - 1][i - 1][j], paper[k - 1][i][j - 1], paper[k - 1][i][j], paper[k - 1][i - 1][j - 1]);

						paper[k][i][j] += map[i][k - i] + map[j][k - j];

					}

                }

            }

        }

		cout << paper[m+n][m][m] << endl;

    }

	return 0;

}

巴特西

soj1767.传纸条

最新文章

热门文章