【P1004】方格取数

本是古典何须时尚 2022-06-07 13:59 186阅读 0赞

[https://www.luogu.org/problem/show?pid=1004][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];(同一个点还要删掉重复的)`

[https_www.luogu.org_problem_show_pid_1004]: https://www.luogu.org/problem/show?pid=1004