P1721 [NOI2016]国王饮水记

NOI2016D2T2

还有一个D1T1咕着没写呢qaq

于是，跳蚤国在每个城市都修建了一个圆柱形水箱，这些水箱完全相同且足够高。一个雨天后，第 $i$ 个城市收集到了高度为 $h_i$ 的水。由于地理和天气因素的影响，任何两个不同城市收集到的水高度互不相同。

跳蚤国王也请来蚂蚁工匠帮忙，建立了一个庞大的地下连通系统。跳蚤国王每次使用地下连通系统时，可以指定任意多的城市，将这些城市的水箱用地下连通系统连接起来足够长的时间之后，再将地下连通系统关闭。由连通器原理，这些城市的水箱中的水在这次操作后会到达同一高度，并且这一高度等于指定的各水箱高度的平均值。

由于地下连通系统的复杂性，跳蚤国王至多只能使用 $k$ 次地下连通系统。

跳蚤国王请你告诉他，首都 $1$ 号城市水箱中的水位最高能有多高？

首先分析一下题目的性质:

那些高度小于首都的点一定没用可以扔掉
我们合并一定先低后高!因为设h_2>h_1,要么先 $h_2$ = $1/2h_1+1/4h_2$ >先 $h_1$ = $1/4h_1+1/2h_2$
最高的前k个被优先合并显然

所以有了这个在原数组上排序一下DP就没后效性了

$dp[i][j]$ 表示到位置i,之前进行了j轮

dp[i][j]=max(\frac{f[k][j-1]+s_i-s_k}{j-k+1})

相当于划分一下然后求平均

这个式子显然可以斜率优化,所求就是一个最大的斜率 $(k-1,s_k-f[i-1][k])$ 和(s_j,j)构成直线斜率

又因为是max,所以维护一个下凸壳,也不难发现 $s_j$ 单增

然而这道题要输出答案后3000位小数......有一个700多行的高精度小数类,我们不可能用对吧

我们遵循如下贪心原则

能一次用2个就不用多个
如果要加入城市进连通器,那水位一定要高与当前

证明1:把一下3个分成两下2个显然会更好吧

证明2:否则的话为什么加?倒流吗?

有了这两个东西,就不难构造了

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,n,m,p;
int h[8192],s[8192];
double f[16][8192];
int g[16][8192];
int a[400];
#define P pair<int,double>
double operator%(const P&a,const P&b) {
	return (b.second-a.second)/(b.first-a.first);
}
void div(int x) {
	ll q=0;
	for(int i=0; i<=p; ++i) {
		q=q*1000000000+a[i];
		a[i]=q/x;
		q%=x;
	}
}

int main() {
	scanf("%d%d%d",&N,&m,&p);
	p=p/9+1;
	scanf("%d",&h[n=1]);
	for(int i=2; i<=N; ++i) {
		int t;
		scanf("%d",&t);
		if(h[1]<t)h[++n]=t;
		//直接弃掉
	}
	sort(h+1,h+n+1);
	if(m>n)m=n;
	for(int i=1; i<=n; ++i)f[0][i]=h[1],s[i]=s[i-1]+h[i];
	//s是前缀和
	int l=14;//你问这一手有什么用?我只能告诉你这是玄学优化,连14次就最优.....
	if(l>m)l=m;
	for(int i=1; i<=l; ++i) {
		static P q[8024];//队列
//		memset(q,0,sizeof(q));

		for(int j=2,l=1,r=0; j<=n; ++j) {
			P c=P(j-2,s[j-1]-f[i-1][j-1]);
			//维护(k-1,s[k]-f[i-1][k])
			for(; l<r&&(q[r-1]%q[r])>(q[r]%c); r--);//盘一下斜率
			q[++r]=c;//把k-1加入决策序列
			P t=P(j,s[j]);//s[j]随j的单调递增而递增
			for(; l<r&&(q[l]%t)<(q[l+1]%t); ++l);
			g[i][j]=q[l].first+1;
			//	printf("%d\n",g[i][j]);
			//记录一下转移最优决策点,注意first代表哪个数 
			f[i][j]=(q[l]%t);
		}
	}
///	puts("QWQ");
	int b[16];

	b[l]=n-(m-l);
	//这个等于最后存活数?
	//当n=m,我们连了l次
	for(int i=l; i; i--)b[i-1]=g[i][b[i]];//找到这些每次选择的序列点 
	a[0]=h[1];
	for(int i=1; i<=l; ++i)a[0]+=s[b[i]]-s[b[i-1]],div(b[i]-b[i-1]+1);//l次连一定先连大的再小的.因为h已经排序了...
	for(int i=b[l]+1; i<=n; ++i)a[0]+=h[i],div(2);//有多余的,可以考虑再勇两个练一下
	printf("%d.",a[0]);
	for(int i=1; i<=p; ++i)printf("%09d",a[i]);
	return 0;
}

夏晓光(loveJY)的博客

庆祝博文过百!