【斜率优化dp】国王饮水记

传送门：UOJ223

NOI2016

---

思路：

• 用$f_{i,j}$表示前j个连通i次以后能达到的最大值，则有：

$$ \large f_{i,j}=\max_\limits{k\leqslant j}{\frac{f_{i-1,k}+pre_j-pre_k}{j-k+1}} $$

• 令：

$$ \large x_k=k-1,y_k=pre_k-f_{i-1,k} $$

• 则：

$$ \large f_{i,j}=\max_\limits{k\leqslant j}{\frac{pre_j-y_k}{j-x_k}} $$

• 对于决策k,l，如果k比l优，则有：

$$ \large \frac{pre_j-y_k}{j-x_k}>\frac{pre_j-y_l}{j-x_l} $$

• 变式得：

$$ \large \frac{j-x_l}{j-x_k}<\frac{pre_j-y_l}{per_j-y_k} $$

• 两边减1得：

$$ \large \frac{x_k-x_l}{j-x_k}>\frac{y_k-y_l}{pre_j-y_k} $$

• 考虑三个决策$p<q<r$且q是有用的决策，可以发现：

$$ \large \frac{x_q-x_p}{j-x_q}>\frac{y_q-y_p}{pre_j-y_q},\frac{x_q-x_r}{j-x_q}\geqslant\frac{y_q-y_r}{pre_j-y_q} $$

• 再次变式得：

$$ \large \frac{pre_j-y_q}{j-x_q}>\frac{y_q-y_p}{x_q-x_p},\frac{pre_j-y_q}{j-x_q}\leqslant\frac{y_q-y_r}{x_q-x_r} $$

• 即：

$$ \large \frac{y_q-y_p}{x_q-x_p}<\frac{pre_j-y_q}{j-x_q}\leqslant\frac{y_q-y_r}{x_q-x_r} $$

• 然后奇妙的发现中间就是$f_{i,j}$，所以：

$$ \large \frac{y_q-y_p}{x_q-x_p}<f_{i,j}\leqslant\frac{y_q-y_r}{x_q-x_r} $$

• 然后这样是过不去的，因为高精度小数太慢了，时间是$O(nkp)$的；
• 考虑用long double求出转移，然后用高精模板模拟转移，时间是$O(nk+kp)$；
• 然后发现转移区间的长度是收敛的，当轮数大于14时就变成1了，然后只需记录前几次转移即可。

注意：不要忘了修改高精小数的位数

---

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>

using namespace std;

#define N 8005

int tt,ww,n,m,p,xx,cnt,a[N],b[N],s[N],q[N];
long double f[30][N],g[30][N],x[N],y[N],pre[N];
const int PREC = 6600;
class Decimal {
	public:
		Decimal();
		Decimal(const std::string &s);
		Decimal(const char *s);
		Decimal(int x);
		Decimal(long long x);
		Decimal(double x);
		
		bool is_zero() const;
		
		// p (p > 0) is the number of digits after the decimal point
		std::string to_string(int p) const;
		double to_double() const;
		
		friend Decimal operator + (const Decimal &a, const Decimal &b);
		friend Decimal operator + (const Decimal &a, int x);
		friend Decimal operator + (int x, const Decimal &a);
		friend Decimal operator + (const Decimal &a, long long x);
		friend Decimal operator + (long long x, const Decimal &a);
		friend Decimal operator + (const Decimal &a, double x);
		friend Decimal operator + (double x, const Decimal &a);
		
		friend Decimal operator - (const Decimal &a, const Decimal &b);
		friend Decimal operator - (const Decimal &a, int x);
		friend Decimal operator - (int x, const Decimal &a);
		friend Decimal operator - (const Decimal &a, long long x);
		friend Decimal operator - (long long x, const Decimal &a);
		friend Decimal operator - (const Decimal &a, double x);
		friend Decimal operator - (double x, const Decimal &a);
		
		friend Decimal operator * (const Decimal &a, int x);
		friend Decimal operator * (int x, const Decimal &a);
		
		friend Decimal operator / (const Decimal &a, int x);
		
		friend bool operator < (const Decimal &a, const Decimal &b);
		friend bool operator > (const Decimal &a, const Decimal &b);
		friend bool operator <= (const Decimal &a, const Decimal &b);
		friend bool operator >= (const Decimal &a, const Decimal &b);
		friend bool operator == (const Decimal &a, const Decimal &b);
		friend bool operator != (const Decimal &a, const Decimal &b);
		
		Decimal & operator += (int x);
		Decimal & operator += (long long x);
		Decimal & operator += (double x);
		Decimal & operator += (const Decimal &b);
		
		Decimal & operator -= (int x);
		Decimal & operator -= (long long x);
		Decimal & operator -= (double x);
		Decimal & operator -= (const Decimal &b);
		
		Decimal & operator *= (int x);
		
		Decimal & operator /= (int x);
		
		friend Decimal operator - (const Decimal &a);
		
		// These can't be called
		friend Decimal operator * (const Decimal &a, double x);
		friend Decimal operator * (double x, const Decimal &a);
		friend Decimal operator / (const Decimal &a, double x);
		Decimal & operator *= (double x);
		Decimal & operator /= (double x);
		
	private:
		static const int len = PREC / 9 + 1;
		static const int mo = 1000000000;
		
		static void append_to_string(std::string &s, long long x);
		
		bool is_neg;
		long long integer;
		int data[len];
		
		void init_zero();
		void init(const char *s);
};
Decimal::Decimal() {
	this->init_zero();
}
Decimal::Decimal(const char *s) {
	this->init(s);
}
Decimal::Decimal(const std::string &s) {
	this->init(s.c_str());
}
Decimal::Decimal(int x) {
	this->init_zero();
	
	if (x < 0) {
		is_neg = true;
		x = -x;
	}
	
	integer = x;
}
Decimal::Decimal(long long x) {
	this->init_zero();
	
	if (x < 0) {
		is_neg = true;
		x = -x;
	}
	
	integer = x;
}
Decimal::Decimal(double x) {
	this->init_zero();
	
	if (x < 0) {
		is_neg = true;
		x = -x;
	}
	
	integer = (long long)x;
	x -= integer;
	
	for (int i = 0; i < len; i++) {
		x *= mo;
		if (x < 0) x = 0;
		data[i] = (int)x;
		x -= data[i];
	}
}
void Decimal::init_zero() {
	is_neg = false;
	integer = 0;
	memset(data, 0, len * sizeof(int));
}
bool Decimal::is_zero() const {
	if (integer) return false;
	for (int i = 0; i < len; i++) {
		if (data[i]) return false;
	}
	return true;
}
void Decimal::init(const char *s) {
	this->init_zero();
	
	is_neg = false;
	integer = 0;
	
	// find the first digit or the negative sign
	while (*s != 0) {
		if (*s == '-') {
			is_neg = true;
			++s;
			break;
		} else if (*s >= 48 && *s <= 57) {
			break;
		}
		++s;
	}
	
	// read the integer part
	while (*s >= 48 && *s <= 57) {
		integer = integer * 10 + *s - 48;
		++s;
	}
	
	// read the decimal part
	if (*s == '.') {
		int pos = 0;
		int x = mo / 10;
		
		++s;
		while (pos < len && *s >= 48 && *s <= 57) {
			data[pos] += (*s - 48) * x;
			++s;
			x /= 10;
			if (x == 0) {
				++pos;
				x = mo / 10;
			}
		}
	}
}
void Decimal::append_to_string(std::string &s, long long x) {
	if (x == 0) {
		s.append(1, 48);
		return;
	}
	
	char _[30];
	int cnt = 0;
	while (x) {
		_[cnt++] = x % 10;
		x /= 10;
	}
	while (cnt--) {
		s.append(1, _[cnt] + 48);
	}
}
std::string Decimal::to_string(int p) const {
	std::string ret;
	
	if (is_neg && !this->is_zero()) {
		ret = "-";
	}
	
	append_to_string(ret, this->integer);
	
	ret.append(1, '.');
	
	for (int i = 0; i < len; i++) {
		// append data[i] as "%09d"
		int x = mo / 10;
		int tmp = data[i];
		while (x) {
			ret.append(1, 48 + tmp / x);
			tmp %= x;
			x /= 10;
			if (--p == 0) {
				break;
			}
		}
		if (p == 0) break;
	}
	
	if (p > 0) {
		ret.append(p, '0');
	}
	
	return ret;
}
double Decimal::to_double() const {
	double ret = integer;
	
	double k = 1.0;
	for (int i = 0; i < len; i++) {
		k /= mo;
		ret += k * data[i];
	}
	
	if (is_neg) {
		ret = -ret;
	}
	
	return ret;
}
bool operator < (const Decimal &a, const Decimal &b) {
	if (a.is_neg != b.is_neg) {
		return a.is_neg && (!a.is_zero() || !b.is_zero());
	} else if (!a.is_neg) {
		// a, b >= 0
		if (a.integer != b.integer) {
			return a.integer < b.integer;
		}
		for (int i = 0; i < Decimal::len; i++) {
			if (a.data[i] != b.data[i]) {
				return a.data[i] < b.data[i];
			}
		}
		return false;
	} else {
		// a, b <= 0
		if (a.integer != b.integer) {
			return a.integer > b.integer;
		}
		for (int i = 0; i < Decimal::len; i++) {
			if (a.data[i] != b.data[i]) {
				return a.data[i] > b.data[i];
			}
		}
		return false;
	}
}
bool operator > (const Decimal &a, const Decimal &b) {
	if (a.is_neg != b.is_neg) {
		return !a.is_neg && (!a.is_zero() || !b.is_zero());
	} else if (!a.is_neg) {
		// a, b >= 0
		if (a.integer != b.integer) {
			return a.integer > b.integer;
		}
		for (int i = 0; i < Decimal::len; i++) {
			if (a.data[i] != b.data[i]) {
				return a.data[i] > b.data[i];
			}
		}
		return false;
	} else {
		// a, b <= 0
		if (a.integer != b.integer) {
			return a.integer < b.integer;
		}
		for (int i = 0; i < Decimal::len; i++) {
			if (a.data[i] != b.data[i]) {
				return a.data[i] < b.data[i];
			}
		}
		return false;
	}
}
bool operator <= (const Decimal &a, const Decimal &b) {
	if (a.is_neg != b.is_neg) {
		return a.is_neg || (a.is_zero() && b.is_zero());
	} else if (!a.is_neg) {
		// a, b >= 0
		if (a.integer != b.integer) {
			return a.integer < b.integer;
		}
		for (int i = 0; i < Decimal::len; i++) {
			if (a.data[i] != b.data[i]) {
				return a.data[i] < b.data[i];
			}
		}
		return true;
	} else {
		// a, b <= 0
		if (a.integer != b.integer) {
			return a.integer > b.integer;
		}
		for (int i = 0; i < Decimal::len; i++) {
			if (a.data[i] != b.data[i]) {
				return a.data[i] > b.data[i];
			}
		}
		return true;
	}
}
bool operator >= (const Decimal &a, const Decimal &b) {
	if (a.is_neg != b.is_neg) {
		return !a.is_neg || (a.is_zero() && b.is_zero());
	} else if (!a.is_neg) {
		// a, b >= 0
		if (a.integer != b.integer) {
			return a.integer > b.integer;
		}
		for (int i = 0; i < Decimal::len; i++) {
			if (a.data[i] != b.data[i]) {
				return a.data[i] > b.data[i];
			}
		}
		return true;
	} else {
		// a, b <= 0
		if (a.integer != b.integer) {
			return a.integer < b.integer;
		}
		for (int i = 0; i < Decimal::len; i++) {
			if (a.data[i] != b.data[i]) {
				return a.data[i] < b.data[i];
			}
		}
		return true;
	}
}
bool operator == (const Decimal &a, const Decimal &b) {
	if (a.is_zero() && b.is_zero()) return true;
	if (a.is_neg != b.is_neg) return false;
	if (a.integer != b.integer) return false;
	for (int i = 0; i < Decimal::len; i++) {
		if (a.data[i] != b.data[i]) return false;
	}
	return true;
}
bool operator != (const Decimal &a, const Decimal &b) {
	return !(a == b);
}
Decimal & Decimal::operator += (long long x) {
	if (!is_neg) {
		if (integer + x >= 0) {
			integer += x;
		} else {
			bool last = false;
			for (int i = len - 1; i >= 0; i--) {
				if (last || data[i]) {
					data[i] = mo - data[i] - last;
					last = true;
				} else {
					last = false;
				}
			}
			integer = -x - integer - last;
			is_neg = true;
		}
	} else {
		if (integer - x >= 0) {
			integer -= x;
		} else {
			bool last = false;
			for (int i = len - 1; i >= 0; i--) {
				if (last || data[i]) {
					data[i] = mo - data[i] - last;
					last = true;
				} else {
					last = false;
				}
			}
			integer = x - integer - last;
			is_neg = false;
		}
	}
	return *this;
}
Decimal & Decimal::operator += (int x) {
	return *this += (long long)x;
}
Decimal & Decimal::operator -= (int x) {
	return *this += (long long)-x;
}
Decimal & Decimal::operator -= (long long x) {
	return *this += -x;
}
Decimal & Decimal::operator /= (int x) {
	if (x < 0) {
		is_neg ^= 1;
		x = -x;
	}
	
	int last = integer % x;
	integer /= x;
	
	for (int i = 0; i < len; i++) {
		long long tmp = 1LL * last * mo + data[i];
		data[i] = tmp / x;
		last = tmp - 1LL * data[i] * x;
	}
	
	if (is_neg && integer == 0) {
		int i;
		for (i = 0; i < len; i++) {
			if (data[i] != 0) {
				break;
			}
		}
		if (i == len) {
			is_neg = false;
		}
	}
	
	return *this;
}
Decimal & Decimal::operator *= (int x) {
	if (x < 0) {
		is_neg ^= 1;
		x = -x;
	} else if (x == 0) {
		init_zero();
		return *this;
	}
	
	int last = 0;
	for (int i = len - 1; i >= 0; i--) {
		long long tmp = 1LL * data[i] * x + last;
		last = tmp / mo;
		data[i] = tmp - 1LL * last * mo;
	}
	integer = integer * x + last;
	
	return *this;
}
Decimal operator - (const Decimal &a) {
	Decimal ret = a;
	// -0 = 0
	if (!ret.is_neg && ret.integer == 0) {
		int i;
		for (i = 0; i < Decimal::len; i++) {
			if (ret.data[i] != 0) break;
		}
		if (i < Decimal::len) {
			ret.is_neg = true;
		}
	} else {
		ret.is_neg ^= 1;
	}
	return ret;
}
Decimal operator + (const Decimal &a, int x) {
	Decimal ret = a;
	return ret += x;
}
Decimal operator + (int x, const Decimal &a) {
	Decimal ret = a;
	return ret += x;
}
Decimal operator + (const Decimal &a, long long x) {
	Decimal ret = a;
	return ret += x;
}
Decimal operator + (long long x, const Decimal &a) {
	Decimal ret = a;
	return ret += x;
}
Decimal operator - (const Decimal &a, int x) {
	Decimal ret = a;
	return ret -= x;
}
Decimal operator - (int x, const Decimal &a) {
	return -(a - x);
}
Decimal operator - (const Decimal &a, long long x) {
	Decimal ret = a;
	return ret -= x;
}
Decimal operator - (long long x, const Decimal &a) {
	return -(a - x);
}
Decimal operator * (const Decimal &a, int x) {
	Decimal ret = a;
	return ret *= x;
}
Decimal operator * (int x, const Decimal &a) {
	Decimal ret = a;
	return ret *= x;
}
Decimal operator / (const Decimal &a, int x) {
	Decimal ret = a;
	return ret /= x;
}
Decimal operator + (const Decimal &a, const Decimal &b) {
	if (a.is_neg == b.is_neg) {
		Decimal ret = a;
		bool last = false;
		for (int i = Decimal::len - 1; i >= 0; i--) {
			ret.data[i] += b.data[i] + last;
			if (ret.data[i] >= Decimal::mo) {
				ret.data[i] -= Decimal::mo;
				last = true;
			} else {
				last = false;
			}
		}
		ret.integer += b.integer + last;
		return ret;
	} else if (!a.is_neg) {
		// a - |b|
		return a - -b;
	} else {
		// b - |a|
		return b - -a;
	}
}
Decimal operator - (const Decimal &a, const Decimal &b) {
	if (!a.is_neg && !b.is_neg) {
		if (a >= b) {
			Decimal ret = a;
			bool last = false;
			for (int i = Decimal::len - 1; i >= 0; i--) {
				ret.data[i] -= b.data[i] + last;
				if (ret.data[i] < 0) {
					ret.data[i] += Decimal::mo;
					last = true;
				} else {
					last = false;
				}
			}
			ret.integer -= b.integer + last;
			return ret;
		} else {
			Decimal ret = b;
			bool last = false;
			for (int i = Decimal::len - 1; i >= 0; i--) {
				ret.data[i] -= a.data[i] + last;
				if (ret.data[i] < 0) {
					ret.data[i] += Decimal::mo;
					last = true;
				} else {
					last = false;
				}
			}
			ret.integer -= a.integer + last;
			ret.is_neg = true;
			return ret;
		}
	} else if (a.is_neg && b.is_neg) {
		// a - b = (-b) - (-a)
		return -b - -a;
	} else if (a.is_neg) {
		// -|a| - b
		return -(-a + b);
	} else {
		// a - -|b|
		return a + -b;
	}
}
Decimal operator + (const Decimal &a, double x) {
	return a + Decimal(x);
}
Decimal operator + (double x, const Decimal &a) {
	return Decimal(x) + a;
}
Decimal operator - (const Decimal &a, double x) {
	return a - Decimal(x);
}
Decimal operator - (double x, const Decimal &a) {
	return Decimal(x) - a;
}
Decimal & Decimal::operator += (double x) {
	*this = *this + Decimal(x);
	return *this;
}
Decimal & Decimal::operator -= (double x) {
	*this = *this - Decimal(x);
	return *this;
}
Decimal & Decimal::operator += (const Decimal &b) {
	*this = *this + b;
	return *this;
}
Decimal & Decimal::operator -= (const Decimal &b) {
	*this = *this - b;
	return *this;
}

long double K(int u,int v){return (y[u]-y[v])/(x[u]-x[v]);}

int main(){
	scanf("%d%d%d",&n,&m,&p);
	scanf("%Lf",&f[0][0]);
	for (int i=2;i<=n;i++){scanf("%d",&xx); if (xx>f[0][0]) a[++cnt]=xx;}
	n=cnt; m=min(m,n); sort(a+1,a+n+1);
	x[0]=-1; y[0]=-f[0][0];
	for (int i=1;i<=n;i++){
		pre[i]=pre[i-1]+a[i]; f[0][i]=f[0][0]; x[i]=i-1; y[i]=pre[i]-f[0][i];
	}
	for (int i=1;i<=min(m,20);i++){
		tt=1,ww=1; q[1]=0;
		for (int j=1;j<=n;j++){
			x[j]=j-1; y[j]=pre[j]-f[i-1][j];
			while (tt<ww && K(q[ww-1],q[ww])>K(q[ww],j)) ww--; q[++ww]=j;
		}
		for (int j=0;j<=n;j++){
			while (tt<ww && K(q[tt],q[tt+1])<=(pre[j]-y[q[tt]])/(j-x[q[tt]])) tt++;
			int k=q[tt]; f[i][j]=(pre[j]-y[k])/(j-x[k]); if (i<=20) g[i][j]=k;
		}
	}
	for (int i=m,j=n;i>=1;i--){
		if (i<=20) b[i]=g[i][j]; else b[i]=j-1; j=b[i];
	}
	b[m+1]=n;
	int X; Decimal Y,F; F=(double)f[0][0];
	for (int i=1,j;i<=m;i++){
		j=b[i]; X=j-1; Y=(double)pre[j]-F;
		F=((Decimal)(double)pre[b[i+1]]-Y)/(b[i+1]-X);
	}
	cout<<F.to_string(p*3/2)<<endl;
	return 0;
}