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