洛谷 P1004 方格取数

2019-08-31 07:14:14来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

洛谷 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;
}

原文链接:https://www.cnblogs.com/poi-bolg-poi/p/11435082.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:剑指offer59:按之字形顺序打印二叉树:[[1], [3,2], [4,5,6,7]]

下一篇:剑指offer62:二叉搜索树的第k个结点,二叉搜索树【左边的元素小