13.传纸条

13.[NOIP2008 提高组] 传纸条
难度：普及+/提高
来源：--

AC代码（C++）：

#include <bits/stdc++.h>
/*
#include <iostream>
#include <cstdio>
#include <algorithm>
*/
using namespace std;
#define N 55
int a[N][N];
int opt[2 * N][N][N];
int main(void)
{
    int k,x,i,j,m,n,add;
    scanf("%d%d",&m,&n);
    for (i = 1;i <= m;i++)
    {
        for (j = 1;j <= n;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    opt[2][1][1] = 0; // The value in the first step is 0
    for (k = 3;k <= m + n;k++)
    { // Start at 3
        for (i = 1;i <= min(k - 1,m);i++)
        { // Note that this is the minimum of k - 1 and m
            for (x = 1;x <= min(k - 1,m);x++) // ditto
            {
                if (i == x)
                {
                    add = a[i][k - i]; // When i = x, only one value is added to the same position
                } 
                else 
                {
                    add = a[i][k - i] + a[x][k - x];
                }
                opt[k][i][x] = max(opt[k][i][x],opt[k - 1][i - 1][x - 1]);
                opt[k][i][x] = max(opt[k][i][x],opt[k - 1][i][x]);
                opt[k][i][x] = max(opt[k][i][x],opt[k - 1][i - 1][x]);
                opt[k][i][x] = max(opt[k][i][x],opt[k - 1][i][x - 1]); // Each person has two directions, multiplication principle, and four possible states
                opt[k][i][x] += add;
             }
        }
    }
    printf("%d\n",opt[m + n][m][m]); // Final status
    return 0;
}

没有注释，自行学习。 注释有了，自行食用

by：ACGO

你的点赞和关注就是我更新题解的最大动力！
-----------------------------点个赞吧 ↓ ！-----------------------------