bzoj 2442: [Usaco2011 Open]修剪草坪【单调栈】
2024-08-23 07:12:49
设f[i]为i不选的最小损失,转移是f[i]=f[j]+e[i[(i-j-1<=k)
因为f是单调不降的,所以f[j]显然越靠右越好因为i-j-1<=k的限制,所以单调栈需要弹栈
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n,m,e[N],q[N],l,r;
long long f[N],ans,mn=1e18;
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
e[i]=read(),ans+=e[i];
for(int i=1;i<=n;i++)
{
while(i-q[l]-1>m&&l<=r)
l++;
f[i]=e[i]+f[q[l]];
while(f[q[r]]>f[i]&&l<=r)
r--;
q[++r]=i;
}
for(int i=n-m;i<=n;i++)
mn=min(mn,f[i]);
printf("%lld\n",ans-mn);
return 0;
}
最新文章
- React视角下的轮播图
- Windows Server 2012 为什么没有“磁盘清理”选项了?
- C# ASP.NET(配置数据库 sql server 地址的两种形式以及配置信息的获取)
- ADO.NET操作数据库(一)
- mybatis前台传给带年月日时分秒的数据给后台,后台接收不到时分秒
- 深入理解Redis:底层数据结构
- JAVA+PHP+阿里云组件纯手工实现POP、SMTP、IMAP开发邮件服务器(二)
- [leetcode]_Same Tree
- Xcode7中添加3DTouch
- 一:Redis的7个应用场景
- JMS学习之路(一):整合activeMQ到SpringMVC 转载:http://www.cnblogs.com/xiaochangwei/p/5426639.html
- hdu 2553 N皇后
- java http缓存
- ASP.NET Core Web API 与 SSL
- c++ string类型的定义及方法
- python笔记---需求文件requirements.txt的创建及使用
- springmvc文件上传功能
- SQL Select语句完整的执行顺序(转)
- 唐顿庄园第一至五季/全集Downton Abbey迅雷下载
- 一些有用的社区论坛,wiki网站(持续更新)
热门文章
- ASP.NET MVC的帮助类HtmlHelper和UrlHelper
- Webdriver概述(selenium对应浏览器版本)
- 用友NC客户端地址
- Linux环境下使用VSCode编译makefile文件的注意事项
- Android RoundedBitmapDrawable:Android官方的圆角图形图象实现方案
- [K/3Cloud] 动态表单打开时传递一个自定义参数并在插件中获取
- 2018/2/17 SpringCloud的一个简单小介绍
- FZU Problem 2132 LQX的作业 (数学题)
- java反射与注解结合使用(根据传入对象输出查询sql)
- JSP的异常处理