tyvj/joyoi 1305 最大子序和
2024-09-16 09:57:51
带了一个转化的单调队列裸题。
转化为前缀和相减即可。
有一点需要注意:从0开始入队而不是1,因为要统计第一个。
(从网上找的对拍程序,结果别人写错了)
/**
freopen("in.in", "r", stdin);
freopen("my.out", "w", stdout);
*/
//// /////////////////////////////
#include <cstdio>
const int N = ; int a[N], sum[N], Q[N], t, e = ; inline void max(int &a, const int b) {
if(a < b) a = b;
return;
} int main() {
//freopen("in.in", "r", stdin);
//freopen("my.out", "w", stdout);
int n, M;
scanf("%d%d", &n, &M);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
sum[i] = sum[i - ] + a[i];
} /*
for(int i = 1; i <= n; i++) {
printf("%d ", sum[i]);
}
printf("\n");
*/ int ans = -0x3f3f3f3f;
for(int i = ; i <= n; i++) { /// !! 0
Q[++t] = i;
if(Q[e] < i - M) {
e++;
}
max(ans, sum[i] - sum[Q[e]]);
while(e < t && sum[i] <= sum[Q[t - ]]) {
Q[--t] = i;
}
}
printf("%d", ans);
return ;
}
AC代码
最新文章
- Debian自带浏览器IceWeasel的中文化
- 编译cscope-15.8a遇到的问题与解决方案
- aspx与ascx,ashx的用法详细的总结介绍
- 【张泽华】android视频教程下载地址及上课源代码
- Android Studio 完美修改应用包名
- Jenkins + robot framework + git持续集成
- 【分享】bootstrap学习笔记
- spring @Component
- hibernate MTM 联合主键
- 前端利用百度开发文档给的web服务接口实现对某个区域周边配套的检索
- L2-001 紧急救援 (25 分) (最短路+路径打印)
- 遍历文件路径python版,java版
- [EasyUI]确认删除
- pytorch解决鸢尾花分类
- 设置div 高度 总结
- Jsp九大内置对象和4大作用域
- Hive 2.1.1安装配置
- 高通QMI协议
- Java基础(六):继承
- DCI改进,发布后作业乱码不能打开