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