【P1004】方格取数-蒲公英云

【P1004】方格取数

https://www.luogu.org/problem/show?pid=1004

这题有两种做法。

第一种是同时考虑两个点，也就是用4个循环。枚举每个点的位置，并计算总分。
f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k-1][l],f[i][j-1][k][l-1],f[i-1][j][k][l-1],f[i][j-1][k-1][l])+a[i][j]+a[k][l];
当(i==k&&j==l)时，多算了一次a[i][j]，因此扣去。

#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std;
int a_max(int a,int b,int c,int d,int e){
    return max(a,max(b,max(c,max(d,e))));
}
int map[11][11];
int n;
int f[11][11][11][11];
int main(){
    memset(map,0,sizeof(map));
    memset(f,0,sizeof(f));
    scanf("%d",&n);
    while(true){
        int a, b, c;
        scanf("%d%d%d",&a,&b,&c);
        if (a==0&b==0&c==0)break;
        map[a][b] = c;
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            for (int k =1;k<=n;k++)
                for (int l=1;l<=n;l++){
                    f[i][j][k][l] = a_max(f[i][j][k][l],f[i-1][j][k-1][l],
                    f[i][j-1][k][l-1],f[i-1][j][k][l-1],f[i][j-1][k-1][l]);
                    f[i][j][k][l] += map[i][j];
                    if (i!=k&&j!=l) f[i][j][k][l]+=map[k][l]; 
                } 
    printf("%d",f[n][n][n][n]);
}

第二种就是考虑到两个点都是从原点出发的，因此满足关系式i+j=k+l(步数相同)。当我们知道一个点的坐标时，我们只需枚举另一个点的坐标，就可以求出另一个点的坐标了。注意判断一下另一个点的坐标是否满足条件。
f[i][j][k]=max(f[i-1][j][k-1],f[i][j-1][k-1],f[i-1][j][k],f[i][j-1][k]))+a[i][j]+a[k][l];(同一个点还要删掉重复的)