【Codevs 2630】宝库通道
2024-09-21 23:11:55
http://codevs.cn/problem/2630/
Solution
预处理f[i][j],代表第j列前i行的代价
枚举上下界,然后做最大子段和,g[i]代表选到第i列的代价,
g[k]=(g[k-1]<0?0:g[k-1])+f[j][k]-f[i-1][k]
复杂度O(n^3)
Notice
注意赋初值
// <2630.cpp> - Tue Oct 18 20:36:24 2016
// This file is made by YJinpeng,created by XuYike's black technology automatically.
// Copyright (C) 2016 ChangJun High School, Inc.
// I don't know what this program is. #include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN=;
int g[MAXN],f[MAXN][MAXN];
int main()
{
freopen("2630.in","r",stdin);
freopen("2630.out","w",stdout);
int n,m,ans=;scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
char ch=getchar();
while(ch!=''&&ch!='')ch=getchar();
f[i][j]=f[i-][j]+(ch==''?-:);
}
for(int i=;i<=n;i++)
for(int j=i;j<=n;j++)
for(int k=;k<=m;k++)
g[k]=(g[k-]<?:g[k-])+f[j][k]-f[i-][k],ans=max(g[k],ans);
printf("%d\n",ans);
return ;
}
最新文章
- 解决iis7只能上传30M文件的限制
- How to read a scientific paper
- PHP中比较两个时间的大小与日期的差值
- ex_KMP--Theme Section
- 001-编译hadoop-2.5.2总结
- ubuntu添加自定义vga输出分辨率
- [AngularJS 2 实践 一]My First Angular App
- (转)C#读取文件路径
- centOS静态ip设置
- vijos1027题解
- [NOI2015]软件包管理器
- centos7下docker启动失败解决
- java4/9 异常处理
- js运行机制详解:event loop
- ES6-课程介绍
- image-set实现Retina屏幕下图片显示详细介绍
- InnoDB log file 设置多大合适?
- 接口与协议学习笔记-AMBA片上通信协议_APB_AHB_AXI_AXI4不同版本(二)
- Codeforces Round #260 (Div. 2) B. Fedya and Maths
- Hibernate查询视图返回null问题说明及解决办法