题目链接:http://hihocoder.com/problemset/problem/1617

题解:一道递推的dp题。这题显然可以考虑两个人同时从起点出发这样就不会重复了设dp[step][i][j]表示走了step步,第一个人在第i行第二个人在第j行第几列就用step减去就行

然后就是简单的递推注意第一个人一定是在第二个人上面的这样才确保不会重复。

#include <iostream>
#include <cstring>
#include <cstdio>
#define inf 0X3f3f3f3f
using namespace std;
int dp[ * ][][];
int a[][] , n;
bool Is(int step , int x , int y) {
int x1 = step - x , y1 = step - y;
return (x1 >= && x1 < n && y1 >= && y1 < n && x >= && x < n && y >= && y < n);
}
int get_val(int step , int x , int y) {
if(Is(step , x , y)) return dp[step][x][y];
return -inf;
}
int main() {
scanf("%d" , &n);
for(int i = ; i < n ; i++) {
for(int j = ; j < n ; j++) {
scanf("%d" , &a[i][j]);
dp[][i][j] = -inf;
}
}
dp[][][] = a[][];
for(int step = ; step <= * n - ; step++) {
for(int i = ; i < n ; i++) {
for(int j = i ; j < n ; j++) {
dp[step][i][j] = -inf;
if(!Is(step , i , j)) continue;
if(i != j) {
dp[step][i][j] = max(dp[step][i][j] , get_val(step - , i - ,j - ));
dp[step][i][j] = max(dp[step][i][j] , get_val(step - , i - , j));
dp[step][i][j] = max(dp[step][i][j] , get_val(step - , i , j - ));
dp[step][i][j] = max(dp[step][i][j] , get_val(step - , i , j));
dp[step][i][j] += a[i][step - i] + a[j][step - j];
}
else {
dp[step][i][j] = max(dp[step][i][j] , get_val(step - , i - , j - ));
dp[step][i][j] = max(dp[step][i][j] , get_val(step - , i - , j));
dp[step][i][j] = max(dp[step][i][j] , get_val(step - , i , j));
dp[step][i][j] += a[i][step - i];
//这里将他们到达同一点时val就取一次那么最大值肯定不是去走同一点的。
}
//这里的转移至要注意第一个人一定在第二个人上面就行,也就是说i>=j是必须的转移时也要注意
}
}
}
printf("%d\n" , dp[ * n - ][n - ][n - ] + a[][] + a[n - ][n - ]);
return ;
}

最新文章

  1. IBatis.Net使用总结(三)-- IBatis实现分页返回数据和总数
  2. LA 5713 秦始皇修路 MST
  3. Android开发自学笔记(Android Studio1.3.1)&mdash;3.Android应用结构解析
  4. PHP之:PHP框架
  5. poi excel export 乱码
  6. nyoj 54-小明的存钱计划
  7. angularjs $watch demo
  8. Eclipse常用功能
  9. 2013流行Python项目汇总
  10. PreResultListener使用
  11. Java 的zip压缩和解压缩
  12. 双数组trie树的基本构造及简单优化
  13. iPhone 尺寸
  14. 配置一个 Confluence 6 环境
  15. Linux系统下tomcat的配置
  16. vim删除单词
  17. 【bzoj3881】[Coci2015]Divljak AC自动机+树链的并+DFS序+树状数组
  18. .net core Ocelot Consul 实现API网关 服务注册 服务发现 负载均衡
  19. HTML5 Canvas,WebGL,CSS Shaders,GLSL的暧昧关系
  20. jQuery之元素查找

热门文章

  1. 第三章、Go-内建容器
  2. dubbo文档笔记
  3. .NET Core 3.0深入源码理解HttpClientFactory之实战
  4. 通俗地说决策树算法(三)sklearn决策树实战
  5. Vue+Typescript中在Vue上挂载axios使用时报错
  6. Css3动画效果,彩色文字效果,超简单的loveHeart
  7. Oracle - SPM固定执行计划(一)
  8. Vector使用方法简单整理
  9. ES6中比较实用的几个特性
  10. 微信小程序商城系统怎样搭建?