POJ 3017 单调队列dp

简介:
Cut the Sequence
Time Limit: 2000MS   Memory Limit: 131072K
Total Submissions:8764   Accepted: 2576

Description

Given an integer sequence { an } of length N, you are to cut the sequence into several parts every one of which is a consecutive subsequence of the original sequence. Every part must satisfy that the sum of the integers in the part is not greater than a given integer M. You are to find a cutting that minimizes the sum of the maximum integer of each part.

Input

The first line of input contains two integer N (0 < N ≤ 100 000), M. The following line contains N integers describes the integer sequence. Every integer in the sequence is between 0 and 1 000 000 inclusively.

Output

Output one integer which is the minimum sum of the maximum integer of each part. If no such cuttings exist, output −1.

Sample Input

8 17
2 2 2 8 1 8 2 1

Sample Output

12


把序列分成若干部分,每一部分的和不超过m。求每一部分里最大值和的最小值。

開始没啥思路,研究了半天,感觉单调队列dp很的精妙,先mark一下,后面慢慢理解吧。

代码:

/* ***********************************************
Author :_rabbit
Created Time :2014/5/13 1:35:25
File Name :C.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
ll que[100100],a[100100],dp[100100];
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
	 //dp 方程:f[i]=f[j]+max(x[j+1],x[j+2],...,x[i]),当中j<i,x[j+1]+x[j+2]+...+x[i]<=m; 
     ll n,m;
	 while(~scanf("%lld%lld",&n,&m)){
		 bool flag=1;
		 for(int i=1;i<=n;i++){
			 scanf("%lld",&a[i]);
			 if(a[i]>m)flag=0;
		 }
		 if(!flag){
			 puts("-1");continue;
		 }
		 ll front=0,rear=0,p=1;
		 dp[1]=a[1];que[rear++]=1;
		 ll sum=a[1];
		 for(ll i=2;i<=n;i++){
			 sum+=a[i];
			 while(sum>m)sum-=a[p++];//区间和小于等于m
			 while(front<rear&&a[i]>=a[que[rear-1]])rear--;//单调严格递减队列
			 que[rear++]=i;
			 while(que[front]<p&&front<rear)front++;//把远离的弹出。
			 dp[i]=dp[p-1]+a[que[front]];
			 for(ll j=front+1;j<rear;j++)
				 dp[i]=min(dp[i],dp[que[j-1]]+a[que[j]]);//枚举队列中的元素,求最优解。
		 }
		 cout<<dp[n]<<endl;
	 }
     return 0;
}



本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5141354.html,如需转载请自行联系原作者

相关文章
iframe 在线预览pdf、word、excel、ppt、txt、图片、视频
iframe 在线预览pdf、word、excel、ppt、txt、图片、视频
|
监控 Java 测试技术
JVM工作原理与实战(二十八):内存溢出和内存泄漏
JVM作为Java程序的运行环境,其负责解释和执行字节码,管理内存,确保安全,支持多线程和提供性能监控工具,以及确保程序的跨平台运行。本文主要介绍了内存溢出与内存泄漏、内存泄漏的常见场景、解决内存溢出的步骤等内容。
322 0
JVM工作原理与实战(二十八):内存溢出和内存泄漏
|
开发框架 安全 .NET
新人小白如何选择阿里云服务器的配置【新手指南】
如何选择阿里云服务器呢?什么配置的阿里云服务器是适合自己的呢?下面我们就来说说如何选择阿里云服务器配置:
2166 0
新人小白如何选择阿里云服务器的配置【新手指南】
|
5天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
16天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1315 5
|
2天前
|
监控 JavaScript Java
基于大模型技术的反欺诈知识问答系统
随着互联网与金融科技发展,网络欺诈频发,构建高效反欺诈平台成为迫切需求。本文基于Java、Vue.js、Spring Boot与MySQL技术,设计实现集欺诈识别、宣传教育、用户互动于一体的反欺诈系统,提升公众防范意识,助力企业合规与用户权益保护。