文档章节

【BZOJ1150】数据备份(动态规划,凸优化)

o
 osc_1ee7cxmx
发布于 2018/08/06 16:57
字数 319
阅读 10
收藏 0

精选30+云产品,助力企业轻松上云!>>>

#【BZOJ1150】数据备份(动态规划,凸优化) ##题面 BZOJ 洛谷 ##题解 在不考虑$K$的情况下很容易$dp$ 如果把$K$考虑进状态显然是$O(n^2)$级别。 所以凸优化一下即可。 注意一下是一个下凸函数,所以是没操作一次就要减去一个权值。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 100100
inline ll read()
{
	ll x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n,K;
ll s[MAX];
struct Node{ll x,y;}f[2][MAX];
Node operator+(Node a,int b){return (Node){a.x+b,a.y};}
bool operator<(Node a,Node b){return a.x<b.x;}
void calc(int C)
{
	memset(f,63,sizeof(f));
	f[0][1]=(Node){0,0};
	for(int i=2;i<=n;++i)
	{
		f[0][i]=min(f[0][i-1],f[1][i-1]);
		f[1][i]=(Node){f[0][i-1].x+(s[i]-s[i-1])-C,f[0][i-1].y+1};
	}
	f[0][n]=min(f[1][n],f[0][n]);
}
int main()
{
	n=read();K=read();
	for(int i=1;i<=n;++i)s[i]=read();
	ll l=0,r=s[n],ans=0;
	while(l<=r)
	{
		ll mid=(l+r)>>1;
		calc(mid);
		if(f[0][n].y<=K)l=mid+1,ans=f[0][n].x+K*mid;
		else r=mid-1;
	}
	printf("%lld\n",ans);
	return 0;
}

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Java线程池

前言 Java中对线程池的抽象是ThreadPoolExecutor类,Executors是一个工具类,内置了多种创建线程池的方法: newFixedThreadPool:固定长度线程池 newCachedThreadPool :可缓存线程池 newSin...

nullpointerxyz
26分钟前
35
0
Python笔记:用Python制作二维码

这些年,二维码在我国的日常使用频率特别大。因为其具有简单及安全性吧!除了用网络工具制作二维码,其实用JavaScript或Python也可以制作二维码,而且更有个性。 示例一(制作普通黑白二维码...

tengyulong
38分钟前
0
0
Redis-初体验/数据结构

定义: Redis 是 C 语言开发的一个开源的(遵从 BSD 协议)高性能键值对(key-value)的内存数据库,可以用作数据库、缓存、消息中间件等。它是一种 NoSQL(not-only sql,泛指非关系型数据库...

心田已荒
40分钟前
15
0
如何在保留订单的同时从列表中删除重复项? - How do you remove duplicates from a list whilst preserving order?

问题: Is there a built-in that removes duplicates from list in Python, whilst preserving order? 是否有内置的程序在保留顺序的同时从Python列表中删除重复项? I know that I can us...

fyin1314
今天
29
0
以太坊智能合约开发常见的10个安全问题

本文介绍CheckMarx安全研究小组通过扫描公开的以太坊智能合约所发现的Solidity智能合约开发中常见的十大安全问题,其中__未检查的外部调用__ 和 高成本循环 分列排行榜前两名。该安全问题排行...

区块链教程
今天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部