题目链接:https://www.luogu.org/problemnew/show/P1719

这道题挺好做的 又是一道练前缀和的题

#include <bits/stdc++.h>
#define Max(a,b) a>b?a:b
#define rep(i,j,n) for(register int i=j;i<=n;i++)
using namespace std;
typedef long long LL;
inline LL read() { LL x=; int f=; char ch=getchar();
while(!isdigit(ch)) { if (ch=='-') f=-; ch=getchar();}
while(isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=getchar(); return x*f;
}
int n,m;
const int N=<<;
int a[N][N];
signed main(){
n=read();
rep(i,,n) rep(j,,n) a[i][j]=read()+a[i-][j]+a[i][j-]-a[i-][j-];
LL ans=;
rep(x1,,n) rep(y1,,n) rep(x2,x1+,n) rep(y2,y1+,n) ans=Max(ans,a[x2][y2]-a[x1-][y2]-a[x2][y1-]+a[x1-][y1-]);
cout << ans << endl ;
return ;
}

前缀和的代码


同样 这需要DP来降低时间复杂度 提高效率orz

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL read () { LL res = ;int f () ;char ch = getchar ();
while (!isdigit(ch)) { if (ch == '-') f = - ;ch = getchar();}
while (isdigit(ch)) res = (res << ) + (res << ) + (ch ^ ) ,ch = getchar(); return res * f ;
}
int n,s[][],f[],ans,p,x,ma;
signed main() {
n=read();
for(register int i=; i<=n; i++) f[i]=-1e9;
for(register int i=; i<=n; i++)
for(register int j=; j<=n; j++) {
x=read();
maxn=Max(maxn,x);
s[i][j]=s[i-][j]+x;
}
ans=-1e9;
for(register int i=; i<=n; i++)
for(register int j=i; j<=n; j++)
for(register int k=; k<=n; k++) {
p=s[j][k]-s[i-][k]; f[k]=max(p,f[k-]+p); ans=max(ans,f[k]);
}
cout << ans << endl ;
return ;
}

最新文章

  1. WKWebView浅析
  2. SQLSERVER 获取datetime日期的查询语句
  3. superSlider实现美女轮播图
  4. 桶装水 送水 消费充值PDA会员管理系统 介绍
  5. 【译】About the Java Technology
  6. System.Diagnostics.Stopwatch
  7. Selenium2学习-025-WebUI自动化实战实例-023-页面快照截图应用之一 -- 常规截图(全页面)
  8. [WPF]解决ListView在没有Items时,水平滚动条不出现的问题
  9. java反射机制入门3
  10. EF 4.1 学习资源汇总
  11. 使用JDBC连接操作数据库
  12. SpringBoot之常用注解
  13. Palindrome Bo (预处理 + 区间DP)
  14. PHP获得用户的真实IP地址
  15. /proc/xxx/maps简要记录
  16. LVS入门篇(三)之LVS的工作模式和调度算法
  17. C#调用C++编写的dll
  18. android Splashy Flash小游戏
  19. Mybatis学习笔记13 - 动态sql之set标签
  20. web.py上传文件并解压

热门文章

  1. set/multiset用法详解
  2. springboot 集成日志 yml配置
  3. hdu 361B
  4. 搭桥(codevs 1002)
  5. 【IntelliJ】IDEA使用--字体、编码和基本设置
  6. 洛谷——P2866 [USACO06NOV]糟糕的一天Bad Hair Day
  7. HDU——2874 Connections between cities
  8. io计算
  9. 使用百度网盘实现自动备份VPS
  10. 开源 免费 java CMS - FreeCMS2.1 会员3.9我的收藏