CF429B. Working out

Summer is coming! It's time for Iahub and Iahubina to work out, as they both want to look hot at the beach. The gym where they go is a matrix a with n lines and m columns. Let number a[i][j] represents the calories burned by performing workout at the cell of gym in the i-th line and the j-th column.

Iahub starts with workout located at line 1 and column 1. He needs to finish with workout a[n][m]. After finishing workout a[i][j], he can go to workout a[i + 1][j] or a[i][j + 1]. Similarly, Iahubina starts with workout a[n][1] and she needs to finish with workout a[1][m]. After finishing workout from cell a[i][j], she goes to either a[i][j + 1] or a[i - 1][j].

There is one additional condition for their training. They have to meet in exactly one cell of gym. At that cell, none of them will work out. They will talk about fast exponentiation (pretty odd small talk) and then both of them will move to the next workout.

If a workout was done by either Iahub or Iahubina, it counts as total gain. Please plan a workout for Iahub and Iahubina such as total gain to be as big as possible. Note, that Iahub and Iahubina can perform workouts with different speed, so the number of cells that they use to reach meet cell may differs.

Two paths of the Iahub and Iahubina must have only one common cell. The time doesn't matter when you consider common points.

首先dp,枚举相遇点,将过程分为相遇前与相遇后两阶段,起终点确定,所以从终点开始dp每个点,而不是每个点推到终点.这些都是显而易见的

问题在于如何保证两个人的路径有且只有一个交点?

要求相遇前无交点,相遇后无交点

可以分类甲和乙是如何相遇的,甲从上面来,乙可以从右边或下边来,这样相遇前就一定不会相交.然后让相遇后也无交点如甲往右走乙往上走就行吗?

不行!!!!!!!!!!!!!!!

如果乙往上走,会和之前甲往上走的轨迹重合!不满足要求

然后可以开始分类讨论,最后得出的结论是只有甲和乙互相横竖穿过,才不会有交点

最后记得把边界用不可能的值封上即可

#include <iostream>
#include <algorithm>
using namespace std;
long long a[1010][1010];
long long dpa[1010][1010], dpar[1010][1010], dpb[1010][1010], dpbr[1010][1010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= n + 1; ++i)
    {
        dpa[i][0] = dpar[i][0] = dpb[i][0] = dpbr[i][0] = dpa[i][m + 1] = dpar[i][m + 1] = dpb[i][m + 1] = dpbr[i][m + 1] = -1e18;
    }
    for (int i = 1; i <= m; ++i)
    {
        dpa[0][i] = dpar[0][i] = dpb[0][i] = dpbr[0][i] = dpa[n + 1][i] = dpar[n + 1][i] = dpb[n + 1][i] = dpbr[n + 1][i] = -1e18;
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j) { cin >> a[i][j]; }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            dpa[i][j] = max((i != 1 ? dpa[i - 1][j] : 0), (j != 1 ? dpa[i][j - 1] : 0)) + a[i][j];//边界之前赋为-1e18了,然而递推开始值应该为0
        }
    }
    for (int i = n; i >= 1; --i)
    {
        for (int j = m; j >= 1; --j)
        {
            dpar[i][j] = max((i != n ? dpar[i + 1][j] : 0), (j != m ? dpar[i][j + 1] : 0)) + a[i][j];
        }
    }
    for (int i = n; i >= 1; --i)
    {
        for (int j = 1; j <= m; ++j)
        {
            dpb[i][j] = max((j != 1 ? dpb[i][j - 1] : 0), (i != n ? dpb[i + 1][j] : 0)) + a[i][j];
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = m; j >= 1; --j)
        {
            dpbr[i][j] = max((j != m ? dpbr[i][j + 1] : 0), (i != 1 ? dpbr[i - 1][j] : 0)) + a[i][j];
        }
    }
    long long res = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            res=max(max(dpa[i-1][j]+dpar[i+1][j]+dpb[i][j-1]+dpbr[i][j+1],dpa[i][j-1]+dpar[i][j+1]+dpb[i+1][j]+dpbr[i-1][j]),res);
        }
    }
    cout << res;
    return 0;
}

反思:问题在于把问题分成相交前后两状态分别判断甲乙路径是否相交是好的,但是只有各自两状态内不相交不够,没有考虑清楚在两状态交界处是否也会相交,对答案产生影响,下一次应该想清楚整个过程,特别是状态交接处的复杂情况