天呢,好神奇的一个DP23333%%%%%

因为1.向左走1格的话相当于当前列和向左走列全选

2.想做走超过1的话可以有上下走替代。而且只能在相邻行向左。

全选的情况只能从第1行和第3行转移,相反全选的情况也只能转移到第1行和第3行。

(大雾,DP太玄乎了,不是很懂2333)

 #include<bits/stdc++.h>
#define LL long long
#define N 100005
#define lowbit(x) x&(-x)
using namespace std;
inline int ra()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
const LL INF=1e16;
LL f[N][];
int a[][N];
inline LL sum(int x, int l, int r)
{
if (l>r) swap(l,r);
LL ret=;
for (int i=l; i<=r; i++) ret+=a[i][x];
return ret;
}
int main()
{
int n=ra();
for (int i=; i<; i++)
for (int j=; j<=n; j++)
a[i][j]=ra();
for (int i=; i<=n; i++)
for (int j=; j<; j++)
f[i][j]=-INF;
f[][]=;
for (int i=; i<=n; i++)
{
for (int j=; j<; j++)
for (int k=; k<; k++)
f[i][j]=max(f[i][j],f[i-][k]+sum(i,j,k));
f[i][]=max(f[i][],f[i-][]+sum(i,,));
f[i][]=max(f[i][],f[i-][]+sum(i,,));
f[i][]=max(f[i][],max(f[i-][],f[i-][])+sum(i,,));
}
cout<<f[n][];
return ;
}

最新文章

  1. Sql Server系列:触发器
  2. Linq常用语法详细
  3. 安利eclipse插件之log4E
  4. Sql Server之旅——第三站 解惑那些背了多年聚集索引的人
  5. CF 256D. Good Sequences(DP)
  6. 创建catalog数据库
  7. LIB 配置文件读写器
  8. Python 协程(gevent)
  9. C# 在本地创建文件夹及子文件夹
  10. 王爽汇编习题2.2(1):给定地址段为0001H,仅通过变化偏移地址寻址,CPU的寻址范围为____到____
  11. 免费好用的阿里云云盾证书服务(https证书)申请步骤
  12. python第三天基础之字符编码
  13. 主流框架的搭建(VUE,React)
  14. win10 死机 无响应
  15. select函数的并发限制和 poll 函数应用举例
  16. javascript forEach方法与jQuery each区别
  17. spark学习11(Wordcount程序-本地测试)
  18. java有几种对象(PO,VO,DAO,BO,POJO)
  19. php rtrim的一个坑,很“二”的问题
  20. winscp介绍与使用

热门文章

  1. 「AMPPZ2014」Petrol
  2. 利用Python进行数据分析笔记-时间序列(时区、周期、频率)
  3. windows下安装redis并部署服务
  4. ImageMagick 将PDF转图片命令
  5. coding 321
  6. CH8 课后习题
  7. 前端面试题CSS一(题目来源网络)
  8. c++中的全排列
  9. 腾讯2019秋招--小q爬塔(dp)
  10. WebEx如何录制电脑内的声音