考试T2修剪草坪
2024-08-31 10:26:46
这题的DP真是刷新了我的理解,竟然还要用队列优化。。。。
#include<iostream>
#include<cstdio>
using namespace std;
long long ans1=;
long long ans,n,k;
const int maxn=1e5+;
long long a[maxn],f[maxn],q[maxn];
inline int read()
{
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
int main()
{
n=read();
k=read();
if(n==)
{
cout<<<<endl;
return ;
}
for(int i=;i<=n;i++)
{
a[i]=read();
ans=ans+a[i];
}
int l=,r=;
for(int i=;i<=n;i++)
{
while(l<=r&&f[q[r]]>=f[i-])
{
r--;
}
q[++r]=i-;
while(l<=r&&q[l]<i-k-)
{
l++;
}
f[i]=f[q[l]]+a[i];
}
for(int i=n-k;i<=n;i++)
{
ans1=min(ans1,f[i]);
}
printf("%lld",ans-ans1);
return ;
}
最新文章
- sscanf格式化输出
- Force.com平台基础--前言
- Convert Sorted Array to Binary Search Tree With Minimal Height
- linux 安装redis
- 安卓接入ShareSDK问题
- 转:QT 的点点滴滴 错误总结
- javascript一些常用函数
- [Google Code Jam (Qualification Round 2014) ] A. Magic Trick
- HDOJ 1423 Greatest Common Increasing Subsequence(dp)
- 剑指Offer——携程笔试题+知识点总结
- 2018蓝桥杯 省赛B题(明码)
- Loadrunner11的安装方法和破解
- locked (a oracle.jdbc.driver.T4CConnection
- 20155225 2016-2017-2 《Java程序设计》第五周学习总结
- 1009 Product of Polynomials (25 分)
- Web前端的状态管理
- Django html标签make_safe
- uoj 67 新年的毒瘤 tarjan求割点
- Python 创建元组tuple
- HTTP缓存机制--客户端缓存(转)