hihocoder #1617 : 方格取数(dp)
2024-08-31 08:40:58
题目链接: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 ;
}
最新文章
- IBatis.Net使用总结(三)-- IBatis实现分页返回数据和总数
- LA 5713 秦始皇修路 MST
- Android开发自学笔记(Android Studio1.3.1)&mdash;3.Android应用结构解析
- PHP之:PHP框架
- poi excel export 乱码
- nyoj 54-小明的存钱计划
- angularjs $watch demo
- Eclipse常用功能
- 2013流行Python项目汇总
- PreResultListener使用
- Java 的zip压缩和解压缩
- 双数组trie树的基本构造及简单优化
- iPhone 尺寸
- 配置一个 Confluence 6 环境
- Linux系统下tomcat的配置
- vim删除单词
- 【bzoj3881】[Coci2015]Divljak AC自动机+树链的并+DFS序+树状数组
- .net core Ocelot Consul 实现API网关 服务注册 服务发现 负载均衡
- HTML5 Canvas,WebGL,CSS Shaders,GLSL的暧昧关系
- jQuery之元素查找