bzoj2442
2024-08-25 06:11:49
题解:
单调队列+dp
f[i]=max(f[j-1]+sum[i]-sum[j])
然后维护f[j-1]-sum[j]单调性
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=;
int n,m,a[N],p[N];
ll sum[N],q[N],f[N];
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)scanf("%d",&a[i]);
for (int i=;i<=n;i++)sum[i]=sum[i-]+a[i];
f[]=a[];p[]=;q[]=-a[];
int l=,r=;
for (int i=;i<=n;i++)
{
if (p[l]+m<i)l++;
f[i]=sum[i]+q[l];
while (l<=r&&q[r]<=f[i-]-sum[i])r--;
p[++r]=i;q[r]=f[i-]-sum[i];
}
printf("%lld",f[n]);
}
最新文章
- 基于面向对象的图片轮播(js原生代码)
- 使用ASP.NET上传图片汇总
- arm嵌入式交叉编译工具链
- Mybatis 异常: The content of elements must consist of well-formed character data or markup
- 透过proxy进行docker pull(Centos6.8)
- 资源Createwindow,对应标识符,绑定窗口
- redis web 客户端工具 redis-admin
- Async/Await - Best Practices in Asynchronous Programming z
- 【转载】正则表达式学习 &; ASCII码表
- .NET开发作业调度(job scheduling) - Quartz.NET
- Pair Project: Elevator Scheduler [电梯调度算法的实现和测试]:刘耀先-11061183,罗凡-11061174
- RHEL7磁盘分区挂载和格式化
- uva10003 Cutting Sticks
- synchronized 与 Lock 的那点事
- MATLAB中的微积分运算(数值&;符号)
- 从DataTable中查询数据
- 图片和base64相互转化
- JAVA作业三
- JavaScript Array some() 方法
- vue-cil和webpack中本地静态图片的路径问题解决方案