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话说不会递推的DP了。。。#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;}
现在只会递归。。。
求不爆栈
NOIP RP++
转载地址:https://blog.csdn.net/li412302070/article/details/14230499 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年02月29日 01时52分08秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
mysql 重置密码_mysql忘记密码如何重置密码,以及修改root密码的三种方法
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
c51写c语言外部ram头文件,C51中访问外部RAM的方法
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