洛谷 P1004 方格取数

目录

• $code$

---

题目

洛谷 p1004 方格取数

思路

方法一：四维dp
设$\text{dp[i][j][k][l]}$表示第一个人走到了$(i,j)$第二个人走到了$(k,l)$的位置时的最大和，因为可以向下走也可以向右走所以$\text{dp[i][j][k][l]=max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])}$$+(i,j)$和$(k,l)$位置的数如果$i=k$并且$j=l$要减去一个。
时间复杂度为$o(n^4)$

$code$

方法一:

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,map[10][10],dp[10][10][10][10];
//dp[i][j][k][l]表示第一个人走到了(i,j)第二个人走到了(k,l)的位置时的最大和
inline int read(){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f?-x:x;
}

int main(){
    n=read();
    int x,y,w;
    while(1){
        x=read(),y=read(),w=read();
        if(!x&&!y&&!w) break;
        map[x][y]=w;
    }
    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){
                    dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+map[i][j]+map[k][l];
                    if(i==k&&j==l) dp[i][j][k][l]-=map[i][j];
                }
            }
        }
    }
    printf("%d\n",dp[n][n][n][n]);
    return 0;
}