【BZOJ1150】数据备份（动态规划，凸优化）

题面

题解

在不考虑\(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;

}

巴特西

【BZOJ1150】数据备份（动态规划，凸优化）

【BZOJ1150】数据备份（动态规划，凸优化）

题面

题解

最新文章

热门文章