VIJOS 1143 三方格取数
发布日期:2022-02-05 18:27:32 浏览次数:15 分类:技术文章

本文共 1949 字,大约阅读时间需要 6 分钟。

背景

JerryZhou同学经常改编习题给自己做。

这天,他又改编了一题。。。。。

描述

设有N*N的方格图,我们将其中的某些方格填入正整数,

而其他的方格中放入0。

某人从图得左上角出发,可以向下走,也可以向右走,直到到达右下角。

在走过的路上,他取走了方格中的数。(取走后方格中数字变为0)

此人从左上角到右下角共走3次,试找出3条路径,使得取得的数总和最大。

格式

输入格式

第一行:N (4<=N<=20)

接下来一个N*N的矩阵,矩阵中每个元素不超过80,不小于0

输出格式

一行,表示最大的总和。

样例1

样例输入

41 2 3 42 1 3 41 2 3 41 3 2 4

样例输出

39

限制

各个测试点1s

提示

多进程DP

就像传纸条。。。恩

第一次居然ce了 忘了memset的cstring了!!!!!

F[X][Y][J][K]表示第一次取到x和y

第二次取到j  x+y-j

第三次取到k x+y-k时取到的最大值

然后要判断 可能走一个格子 这时候另一次要+0

#include
#include
#include
using namespace std;int s[22][22];int f[22][22][22][22];int m,a,b,c;int move(int bu,int x1,int x2,int x3){ int y1=bu-x1,y2=bu-x2,y3=bu-x3; if(x1==x2&&x2==x3)return s[x1][y1]; if(x1==x2&&x2!=x3)return s[x1][y1]+s[x3][y3]; if(x1!=x2&&x2==x3)return s[x1][y1]+s[x3][y3]; if(x1==x3&&x2!=x3)return s[x1][y1]+s[x2][y2]; if(x1!=x2&&x2!=x3&&x3!=x1)return s[x1][y1]+s[x2][y2]+s[x3][y3]; return 0;}int work(int x,int y,int j,int k){ int bu=x+y; if(x>m||y>m||j>m||k>m||bu-j>m||bu-k>m)return 0; if(x<=0||y<=0||j<=0||k<=0||bu-j<=0||bu-k<=0)return 0; if(f[x][y][j][k]!=-1)return f[x][y][j][k]; f[x][y][j][k]=max(f[x][y][j][k],work(x-1,y,j,k)+move(x+y,x,j,k)); f[x][y][j][k]=max(f[x][y][j][k],work(x-1,y,j-1,k)+move(x+y,x,j,k)); f[x][y][j][k]=max(f[x][y][j][k],work(x-1,y,j,k-1)+move(x+y,x,j,k)); f[x][y][j][k]=max(f[x][y][j][k],work(x-1,y,j-1,k-1)+move(x+y,x,j,k)); f[x][y][j][k]=max(f[x][y][j][k],work(x,y-1,j,k)+move(x+y,x,j,k)); f[x][y][j][k]=max(f[x][y][j][k],work(x,y-1,j-1,k)+move(x+y,x,j,k)); f[x][y][j][k]=max(f[x][y][j][k],work(x,y-1,j,k-1)+move(x+y,x,j,k)); f[x][y][j][k]=max(f[x][y][j][k],work(x,y-1,j-1,k-1)+move(x+y,x,j,k)); return f[x][y][j][k];}int main(){ scanf("%d",&m); memset(f,-1,sizeof(f)); for(a=1;a<=m;a++) for(b=1;b<=m;b++) scanf("%d",&s[a][b]); cout<
<<'\n'; return 0;}

话说不会递推的DP了。。。

现在只会递归。。。

求不爆栈

NOIP RP++

转载地址:https://blog.csdn.net/li412302070/article/details/14230499 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:VIJOS 1493 传纸条
下一篇:VIJOS 1740 聪明的质检员

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年02月29日 01时52分08秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql 重置密码_mysql忘记密码如何重置密码,以及修改root密码的三种方法 2019-04-21
python-docx tables后追加内容_Mac brew安装MySQL8.0.21后忘记密码(重置密码篇) 2019-04-21
python中两个时间相减结果转为小时_Python起步(二)基础数据类型1 2019-04-21
定义泛化。举个例子_网易考拉应用的dubbo泛化调用,是如何实现的? 2019-04-21
mysql里可以用cube吗_sql server的cube操作符使用详解_mysql 2019-04-21
php mysql 图书_使用PHP+MySQL来对图书管理系统进行构建 2019-04-21
单片机c语言 int1,51单片机into、int1中断计数c语言源程序.doc 2019-04-21
c语言课程设计工资管理建库,C语言课程设计工资管理系统参考.doc 2019-04-21
c语言case中途跳出,break语句在switch结构语句中的作用是终止某个case,并跳出switch结构语句。... 2019-04-21
c51写c语言外部ram头文件,C51中访问外部RAM的方法 2019-04-21
51c语言产生随机证书,基于51单片机的随机数产生器设计-LCD1602-KEY-(电路图+程序源码)... 2019-04-21
C语言编写程序计算高考倒计时天数,基于51单片机LCD12864大字符校时万年历带高考倒计时程序... 2019-04-21
c语言打开一个html文件路径,C语言文件处理-C语言文件的打开和关闭 2019-04-21
普职融通信息技术课本C语言,“三步走”扎实推进“普职融通”办学新模式 2019-04-21
Android多个签名,【Android】Android批量重签名 2019-04-21
html unicode编码转换,JS实现的Unicode编码转换操作示例 2019-04-21
html页面角落放动漫人物,L2Dwidget.js L2D网页动画人物添加 2019-04-21
html图片水平居中,CSS制作图片水平垂直居中 2019-04-21
水滴pin安卓版apk_财务报销管理系统 2019-04-21
平面设计师okr_设计团队的KPI/OKR如何制定? 2019-04-21