1875: 蛤玮的财宝

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 530  Solved: 116

SubmitStatusWeb Board

Description

蛤玮和他的妹子出海游玩,不小心遭遇了海难,他们醒来之后发现自己到了一座金银岛.岛主非常好心的告诉他们在岛的另一边有船可以送他们回家.
这座岛可以看成n*m的矩阵,蛤玮他们在位置(1,1),而船在位置(n,m).蛤玮发现金银岛遍地都是金子,每个格子里有价值a[i,j]的金子,他和妹子打算在回去的路上带一些走.如果他们路过了位置(i,j),就可以假装系鞋带捡走地上的金子.为了不引起怀疑,他们在走的时候只能往接近码头的方向走,即如果蛤玮现在在(i,j),他只能移动到(i+1,j)或者(i,j+1).为了能拿走更多的金子,蛤玮和妹子决定装作互相不认识,这样他们就可以分开走,从而拿到更多的金子.
蛤玮和他妹子想知道他们最多能拿走多少金子.
注意如果蛤玮和他妹子经过了相同的地方,只能得到一次金子,因为地上的捡完就没有了.

Input

 
T(1<=T<=10),表示数据组数.
每组数据第一行n,m(1<=n,m<=100),接下来n行,每行m个数,第i行第j列的值a[i,j](1<=a[i,j]<=1000)表示位置(i,j)的金子的价值.

Output

 
每组数据输出一行,蛤玮和他妹子能拿到的金子总价的最大值.

Sample Input

1
2 2
2 1
1 2

Sample Output

6
同上一道双线DP类似思路,不过注意最后加上两个起点和终点的值即可。

#include<bits/stdc++.h>
using namespace std;
#define CIN(a) scanf("%d",&a)
#define ql(a) memset(a,0,sizeof(a))
int dp[210][105][105];
int e[105][105];
int main()
{
int t,i,j,n,m;
int x1,x2,k;
CIN(t);
while(t--){ql(e),ql(dp);
CIN(n),CIN(m);
for(i=1;i<=n;++i)
for(j=1;j<=m;++j) CIN(e[i][j]);
for(k=1;k<n+m-2;++k)
for(x1=1;x1<=n;++x1)
for(x2=1;x2<=n;++x2){
int y1=k+2-x1,y2=k+2-x2;
if(x1==x2||y1<0||y2<0||y1>m||y2>m) continue;
dp[k][x1][x2]=max(max(dp[k-1][x1][x2],dp[k-1][x1][x2-1]),max(dp[k-1][x1-1][x2],dp[k-1][x1-1][x2-1]))+e[x1][y1]+e[x2][y2];
}

cout<<max(dp[k-1][n-1][n],dp[k-1][n][n-1])+e[n][m]+e[1][1]<<endl;
}
return 0;
}

注意处理起点如果没有初始化dp[0][x1][x2]的话最后切记加上e[1][1].

也可以选择先处理dp[0]不过不划算啦

最新文章

  1. Angularjs select的使用
  2. Linux 通配符
  3. 在Ubuntu-14.04.3配置并成功编译Android6_r1源码
  4. OpenStack collectd的从零安装客户端
  5. oc-20-多态
  6. 01-08-02【Nhibernate (版本3.3.1.4000) 出入江湖】二级缓存:NHibernate自带的HashtableProvider
  7. SAP BW 通过视图创建数据源(无单位)
  8. iOS合并静态库文件
  9. init()和onEnter()方法的区别
  10. Ubuntu18.04教程
  11. NOI2004郁闷的出纳员
  12. ES6 Symbol数据类型和set-map 数据结构
  13. centos rancher 通过本机 docker images 新增container
  14. js循环json得到 键和值
  15. CentOS 7.0关闭服务器的防火墙服务命令
  16. Linux学习笔记之五————Linux常用命令之用户、权限管理
  17. Cookie浅谈
  18. android project
  19. HTML表单与输入实例
  20. 自定义SAP用户密码规则

热门文章

  1. tcp状态机
  2. Jira中Activity Stream中显示Localhost不能正常访问的处理
  3. PHP输出缓冲控制- Output Control 函数应用详解
  4. MBProgressHUD ---
  5. [Session] SessionHelper2---C#关于Session高级操作帮助类 (转载)
  6. LeetCode 11. Container With Most Water (装最多水的容器)
  7. 使用DBMS_LOCK控制程序并发
  8. 【IDEA填坑】springboot整合ssm框架
  9. css不受高度限制实现文本超出隐藏并以省略号结束
  10. Xenserver之设置Xenserver和VM机开机自动启动
  11. Java strictfp有什么作用
  12. tornado的异步效果
  13. Database学习 - mysql数据类型约束
  14. windows安装nginx并存放静态资源
  15. reportviewer需要的3个引用
  16. [Java学习] 再谈Java包
  17. (转)Python科学计算之Pandas详解,pythonpandas
  18. 怎么掌握微信小程序的取值、传值、数据存储
  19. systemctl的常用命令
  20. Maven入门指南(一)