luogu2034
2024-10-06 15:10:34
/*
* 正难则反
* f[i] 表示前 i 个数中被删除的数的最小和
* f[i] = min(f[j]) + num, i - k + 1 <= j < i;
* 单调队列维护
*/
#include <bits/stdc++.h> #define LL long long const int N = 1e5 + ; LL tot, d, n, k;
LL p[N], head = , tail = ;
LL q[N], f[N], ans; int main() {
std:: cin >> n >> k;
for(int i = ; i <= n; ++ i)
{
std:: cin >> d;
tot += d;
f[i] = q[head] + 1LL * d;
while(head <= tail && q[tail] >= f[i]) tail --;
q[++ tail] = f[i], p[tail] = i;
while(head <= tail && p[head] < i - k) head ++;
}
for(int i = n - k; i <= n; ++ i) ans = std:: max(ans, 1LL * tot - 1LL * f[i]);
printf("%lld", ans);
}
最新文章
- Android下载图片/调用系统相机拍照、显示并保存到本地
- linux 共享内存实现
- datagrid点击标题进行排序
- 更改Apache默认网站根目录
- 【转】Entity Systems
- 理解C#系列 / 核心C# / 变量
- Calculating a bearing between points in location-aware apps
- linux查看端口号是否被占用
- Caused by: java.lang.NullPointerException, java.lang.reflect.InvocationTargetExc
- 如果不知道MySQL当前使用配置文件(my.cnf)的路径的解决方法
- ubuntu 下编译内核
- 关于方法中的形参out
- R语言——绘图函数深入学习
- 处理 Vue 单页面应用 SEO 的另一种思路
- 完全理解 Python 迭代对象、迭代器、生成器(转)
- 【公众号系列】SAP HANA 平台的优势
- MySQL之记录相关操作
- Oracle插入语句日期格式设置
- freeType移植总结①——使用keil编译freeType2库
- Jenkins的环境部署