博客

P1006 [NOIP2008 提高组] 传纸条

由于第一个传完之后就不再帮了，所以可以转化为两个人同时进行，判断一下相同地点时就行了

#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
#include <stack>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <iomanip> //保留小数setprecision
#define endl '\n'
#define PI acos(-1.0) // 3.1415
#define Buff std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define inf 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define memc(a, b) memcpy(a, b, sizeof(b))
#define lowerbit(x) x & -x
#define fi(a, n, b) fill(a, a + n, b)
#define ll long long
#define ull unsigned long long
#define eps 1e-10
//#pragma GCC optimize(2)
using namespace std;
const int N = 55, M = 1e5 + 7;

int n, m;
int w[N][N];
int f[N * 2][N][N];
//第一维是横纵坐标之和，第二，三维是第一次和第二次的横坐标
//思想就是让两次同时走
//如果要做到同一个地方，必须i1+j1=i2+j2
int main()
{
    int n, m;
    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 <= n + m; k++)//第一个点和为2
        for (int i1 = 1; i1 <= n; i1++)//第一个横坐标
            for (int i2 = 1; i2 <= n; i2++)//第二个横坐标
            {
                int j1 = k - i1, j2 = k - i2;
                if (j1 >= 1 && j1 <= m && j2 >= 1 && j2 <= m)//纵坐标在范围之内
                {
                    int t = w[i1][j1];
                    if (i1 != i2)//不重合就计算两个点的w值
                        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][i2 - 1] + t);//一个右一个下
                    x = max(x, f[k - 1][i1 - 1][i2] + t);//一个右一个下
                    x = max(x, f[k - 1][i1][i2] + t);//两个右
                }
            }
    cout << f[n + m][n][n] << endl;
    return 0;
}