2853 方格游戏(三维棋盘)

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond

题解

 查看运行结果

题目描述 Description

菜菜看到了一个游戏,叫做方格游戏~

游戏规则是这样的:

在一个n*n的格子中,在每个1*1的格子里都能获得一定数量的积分奖励,记左上角为(1,1),右下角为(n,n)。游戏者需要选择一条(1,1)到(n,n)的路径,并获得路径上奖励的积分。对于路径当然也有要求啦,要求是只能往坐标变大的方向走【从(x,y)到(x+1,y)或者(x,y+1)】,走过2n-1个区域到达(n,n)。当然,获得的积分最高的就能取胜啦。

这时,菜菜看到了他的好友月月,于是邀请她来玩双人版的。双人版的规则就是在单人版的基础上加上一条两人的路线不能相同。月月知道菜菜的很聪明,怕输得太惨,就不太愿意和他玩。菜菜可慌了,于是定义了一个公平值D,这个公平值等于俩人所选择的路径所能获得的积分一一对应相减的差的绝对值之和,即D=sigma (|kxi-kyi|)|(kx,ky分别为菜菜,月月走过的每一个区域的丛林系数)。不过这可是个庞大的计算任务,菜菜找到了你,请你帮忙计算公平值的最大值。

输入描述 Input Description

    第一行,一个正整数n

    接下来的n行,每行n个整数,表示丛林中每个区域的公平值

输出描述 Output Description

一个整数Dmax,即公平值的最大值

样例输入 Sample Input

4

1 2 3 4

1 5 3 2

8 1 3 4

3 2 1 5

样例输出 Sample Output

13

数据范围及提示 Data Size & Hint

对于20%的数据,保证0<n≤20

对于50%的数据,保证0<n≤50

对于100%的数据,保证0<n≤100且对于所有的i,j保证|Kij|≤300

首先这题四维会爆空间。

所以就学了一下用三维表示。

前提:

1.设两个人的坐标分别为A,B;

2.n*n的方格,从(1,1)点到(n,n)点需要的总步数为2*n+1(n个横,n个列,其中有一个重复)

我们用k来表示步数

我们用i来表示在第k步A的横坐标为i

       用j来表示在第k步B的横坐标为j

那么A的坐标可以表示为(i,k-i+1)

       B的坐标可以表示为(j,k-j+1)

对于每一个点(i,j)

同样有四中情况转移而来

1.A从上到下    dp[i-1][j][k-1]

2.B从上到下    dp[i][j-1][k-1]

3.AB同时从上到下dp[i-1][j-1][k-1]

4.AB同时从左往右dp[i][j][k-1]

然后再加上这个点的值就好

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdlib>
 6 using namespace std;
 7 void read(int &n)
 8 {
 9     char c='+';int x=0;bool flag=0;
10     while(c<'0'||c>'9')
11     {c=getchar();if(c=='-')flag=1;}
12     while(c>='0'&&c<='9')
13     {x=x*10+(c-48);c=getchar();}
14     flag==1?n=-x:n=x;
15 }
16 int n;
17 int dp[101][101][301];
18 int a[101][101];
19 int ans=0;
20 int main()
21 {
22     read(n);
23     for(int i=1;i<=n;i++)
24         for(int j=1;j<=n;j++)
25             read(a[i][j]);
26     // a :(i,k-i+1)
27     // b :(j,k-j+1)
28     for(int k=1;k<=2*n-1;k++)
29     {
30         for(int i=1;i<=n&&i<=k;i++)
31             for(int j=1;j<=n&&j<=k;j++)
32             {
33                 dp[i][j][k]=max(dp[i-1][j][k-1],dp[i][j][k]);
34                 dp[i][j][k]=max(dp[i][j-1][k-1],dp[i][j][k]);
35                 dp[i][j][k]=max(dp[i-1][j-1][k-1],dp[i][j][k]);
36                 dp[i][j][k]=max(dp[i][j][k-1],dp[i][j][k]);
37                 dp[i][j][k]+=abs(a[i][k-i+1]-a[j][k-j+1]);
38             }
39     }
40     printf("%d",dp[n][n][2*n-1]);
41     return 0;
42 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏目标检测和深度学习

教程 | 如何使用DeepFake实现视频换脸

1.5K2
来自专栏深度学习之tensorflow实战篇

推荐算法图推荐-基于随机游走的personalrank算法实现

推荐算法图推荐 基于图的模型(graph-based model)是推荐系统中的重要内容。其实,很多研究人员把基于邻域的模型也称为基于图的模型,因为可以把基于邻...

1.9K9
来自专栏数据派THU

手把手教你深度学习强大算法进行序列学习(附Python代码)

本文共3200字,建议阅读10分钟。 本文将教你使用做紧致预测树的算法来进行序列学习。

1934
来自专栏机器之心

EMNLP 2018 | 结合通用和专用NMT的优势,CMU为NMT引入「语境参数生成器」

神经机器翻译(NMT)无需单独训练或调整系统的任何部分就可以直接建模源语言到目标语言的映射。这使得 NMT 快速发展,并在许多大规模环境中成功应用 (Wu et...

1381
来自专栏牛客网

腾讯应用研究一面 武汉

腾讯应用研究武汉现场一面 一共20分钟。 (比我内推的三轮面试都缺少一点技术含量,内推面试会问我项目,跟我有交流或者提建议,这次就感觉随便找点东西问问,然后最后...

51816
来自专栏iOSDevLog

《 Julia 数据科学应用》各章思考题答案

1.如果你以前没有用过 Julia,那么 Juno 是最安全的选择。如果不使用 Juno,那么带有最新 Julia 内核(在 IJulia 界面右上方)的 IJ...

1134
来自专栏小樱的经验随笔

【机器学习笔记之一】深入浅出学习K-Means算法

摘要:在数据挖掘中,K-Means算法是一种 cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。 ...

3039
来自专栏逍遥剑客的游戏开发

快速LightMap烘焙

1093
来自专栏机器之心

从基础概念到实现,小白如何快速入门PyTorch

3677
来自专栏磐创AI技术团队的专栏

【Github 4K星】BAT头条滴滴小米等笔试面经+深度学习/算法/NLP资源汇总!

最近,在GitHub上有位id为imhuay的热心人带头建立了一个关于国内知名互联网企业笔试和面试经验的资源库,光从名称上就能看出其内容有多丰富:《2018/2...

2383

扫码关注云+社区

领取腾讯云代金券