【GDOI2014模拟】JZOJ2020年8月14日提高组服务器

题目

Time and Memory Limits

Description

我们需要将一个文件复制到n个服务器上，这些服务器的编号为S1, S2, …, Sn。

首先，我们可以选择一些服务器，直接把文件复制到它们中；将文件复制到服务器Si上，需要花费ci > 0的置放费用。对于没有直接被复制文件的服务器Si来说，它依次向后检查Si+1, Si+2, …直到找到一台服务器Sj：Sj中的文件是通过直接复制得到的，于是Si从Sj处间接复制得到该文件，这种复制方式的读取费用是j – i（注意j>i）。另外，Sn中的文件必须是通过直接复制得到的，因为它不可能间接的通过别的服务器进行复制。我们设计一种复制方案，即对每一台服务器确定它是通过直接还是间接的方式进行复制（Sn只能通过直接方式），最终使每一台服务器都得到文件，且总花费最小。

Input

输入文件的第一行有一个整数n，表示服务器的数目。输入文件的第二行有n个整数，顺数第i个表示ci：在Si上直接复制文件的费用。

Output

输出文件中只包含一个整数，即最少需要花费的费用。

Sample Input

10

2 3 1 5 4 5 6 3 1 2

Sample Output

Data Constraint

60%的数据中，1 <= n <= 1 000

100%的数据中，1 <= n <= 1 000 000

80%的数据中， 1 <= ci <= 50

100%的数据中，1 <= ci <= 1 000 000 000

最终结果可能较大，请注意选择适当的数据类型进行计算。

Hint

题解

题意

给出\(n\)个点

每个点可以选择两种操作

一种是直接复制，费用为\(a_i\)

一种是间接复制，费用为\(i\)后面第一个直接复制的\(j\)的\(j-i\)

\(n\)号点必须直接复制

问最小代价

分析

考虑\(DP\)

设\(f[i]\)表示\(i\)点直接复制和间接复制的总和

那么转移

\(f[i]=min\{f[j]+j*(j-i)-\dfrac{(j-i)(j+i-1)}{2}\}\)

转移\(n^2\)，过不了

思考优化

发现可以斜率优化

优化

\(\dfrac{f[j]-f[k]+\dfrac{j^2-k^2+k-j}{2}}{j-k}<i(j>k)\)

单调队列维护

Code

#include<bits/stdc++.h>

using namespace std;

long long n,l,r,ans,f[1000005],q[1000005],a[1000005];

long long read()

{

	long long res=0;char ch;

	ch=getchar();

	while (ch<'0'||ch>'9') ch=getchar();

	while (ch>='0'&&ch<='9')

	{

		res=(res<<1)+(res<<3)+(ch-'0');

		ch=getchar();

	}

	return res;

}

long long get(long long l,long long r)

{

	return r*(r-l)-(r+l-1)*(r-l)/2;

}

double slope(long long x,long long y)

{

	return (f[x]-f[y]+(x*x-y*y+y-x)/2)*1.0/(x-y);

}

int main()

{

	n=read();

	for (long long i=1;i<=n;i++)

		a[i]=read();

	f[n]=a[n];

	l=1;

	r=1;

	q[1]=n;

	for (long long i=n-1;i;i--)

	{

		while (l<r&&slope(q[l],q[l+1])>=i) l++;

		f[i]=a[i]+f[q[l]]+get(i+1,q[l]);

		while (l<r&&slope(q[r-1],q[r])<slope(q[r],i)) r--;

		q[++r]=i;

	}

	ans=99999999999999;

	for (long long i=1;i<=n;i++)

		ans=min(ans,f[i]+get(1,i));

	printf("%lld\n",ans);

	return 0;

}

巴特西

【GDOI2014模拟】JZOJ2020年8月14日提高组服务器

【GDOI2014模拟】JZOJ2020年8月14日提高组服务器

题目

Time and Memory Limits

Description

Input

Output

Sample Input

Sample Output

Data Constraint

Hint

题解

题意

分析

Code

最新文章

热门文章

巴特西

【GDOI2014模拟】JZOJ2020年8月14日提高组 服务器

【GDOI2014模拟】JZOJ2020年8月14日提高组 服务器

题目

Time and Memory Limits

Description

Input

Output

Sample Input

Sample Output

Data Constraint

Hint

题解

题意

分析

Code

最新文章

热门文章

【GDOI2014模拟】JZOJ2020年8月14日提高组服务器

【GDOI2014模拟】JZOJ2020年8月14日提高组服务器