https://codeforces.com/problemset/problem/429/B

这个题目之前写过,不过好像。。忘记了,今天又没有写出来,应该之前没有想明白。。。

这个应该算一个四角dp(网上说的,感觉很符合),所以呢就是要从四个角进行dp,

就是先对四个角到对角的一个dp,然后就是枚举每一个位置,找其中最大的。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#define inf 0x3f3f3f3f
#define debug(x) cout<<"-----"<<" x = "<<x<<"-----"<<endl
using namespace std;
typedef long long ll;
const int mod = 1e8;
const int maxn = 5e5 + ;
ll dp1[][], dp2[][], dp3[][], dp4[][];
int a[][];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
scanf("%d", &a[i][j]);
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
dp1[i][j] = a[i][j] + max(dp1[i - ][j], dp1[i][j - ]);
}
}
for(int i=n;i>=;i--)
{
for(int j=;j<=m;j++)
{
dp2[i][j] = a[i][j] + max(dp2[i + ][j], dp2[i][j - ]);
}
}
for(int i=;i<=n;i++)
{
for(int j=m;j>=;j--)
{
dp3[i][j] = a[i][j] + max(dp3[i - ][j], dp3[i][j + ]);
}
}
for(int i=n;i>=;i--)
{
for(int j=m;j>=;j--)
{
dp4[i][j] = a[i][j] + max(dp4[i + ][j], dp4[i][j + ]);
}
}
ll ans = ;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
ans = max(ans, dp1[i - ][j] + dp4[i + ][j] + dp2[i][j - ] + dp3[i][j + ]);
ans = max(ans, dp1[i][j - ] + dp4[i][j + ] + dp2[i + ][j] + dp3[i - ][j]);
}
}
printf("%lld\n", ans);
return ;
}

最新文章

  1. pipedata3d User Guide
  2. C#生成二维码示例
  3. 【转】VI/VIM常用命令
  4. 通用表表达式(Common Table Expression)
  5. hdu1166树状数组
  6. 搭建基于Linux6.3+Nginx1.2+PHP5+MySQL5.5的Web服务器全过程----转载
  7. 读书笔记《CSS权威指南》
  8. Java中常见的数据结构
  9. JQuery实战总结二 横向纵向菜单下拉效果图
  10. Tiny4412模式跳转
  11. 肺结节CT影像特征提取(三)——肺结节CT影像特征提取系统软件设计
  12. linux三剑客之grep
  13. 【原创】STM32下波特率计算详解
  14. 牛客网Wannafly挑战赛25A 因子(数论 素因子分解)
  15. 最短路径之Bellman-Ford算法
  16. MySQL Execution Plan--NOT EXISTS子查询优化
  17. oracle解除锁表【原】
  18. Ubuntu 编译安装 Xdebug
  19. Ubuntu安装时没注册root用户密码,怎么登录root
  20. Java -- 异常的捕获及处理 -- throws与throw关键字

热门文章

  1. std::string::assign函数
  2. java解惑之常常忘记的事
  3. 如何改变Xcode字体大小?
  4. android学习笔记——利用BaseAdapter生成40个列表项
  5. 小白们错过就没了!Python基础之注释&amp;变量命名
  6. L23模型微调fine tuning
  7. Daily Scrum 12/23/2015
  8. C#开发BIMFACE系列31 服务端API之模型对比2:获取模型对比状态
  9. [YII2] 文件上传类
  10. 来个干货——使用VS2019发布.NET Core程序并部署到IIS的最新教程