傳送門

首先比$h_1$小的肯定沒用，直接無視

然后考慮合并的順序

①在無限制的情況下，合并多個不如一個一個合并

$a<b<c$時，$\frac{\frac{a+b}{2}+c}{2}>\frac{a+b+c}{3}$

②先合并小的比先合并大的優

整理一下，就是把$>h_1$的從小到大排序，然后每次把當前的和序列中靠前的若干個合并

顯然是個斜率優化的模型

設$f_{k,n}$表示前$n$個合并$k$次的最大值

$$f_{k,n}=\underset{1\le i<n}{\max }\frac{f_i+S_n?S_i}{n?i+1}$$

推一下式子發現很惡心

但注意到這個式子本身就是斜率的形式

可以看成所有$(i?1,S_i?f_i)$到$(n,S_n)$的最大斜率

意識流一波，維護一個下凸殼，每次最優決策是過$(n,S_n)$的一條與凸殼切于端點的直線，可以三分一下……

注意到$h$嚴格單調增，所以$(n,S_n)$本身就組成了下凸殼

對于兩個決策$k_1,k_2$,設$i$是$k_2$優于$k_1$的$(i,S_i)$,即$(k_1?1,S_{k_1}?f_{k_1}),(k_2?1,S_{k_2}?f_{k_2}),(i,S_i)$往上翹

如圖，$k_{i?1,i}>k_{k_2,i}$,又因為$k_{i,i+1}>k_{i?1,i}$,所以對于$i+1$ $k_2$仍然更優

所以可以把$k_1$彈掉

這樣可以做到$O(nkp)$ 這里因為最多只能取$n?1$次合并，所以$n,k$是同階的

然后可以用低精度算$dp$并記錄決策，最后用高精度算一次 復雜度$O(nk+np)$

// This is an empty program with decimal lib#include <cstdlib> #include <cstring> #include <string> #include <cctype> #include <cstdio> // ---------- decimal lib start ----------const int PREC = 3500;class Decimal {public:Decimal();Decimal(const std::string &s);Decimal(const char *s);Decimal(int x);Decimal(long long x);Decimal(long double x);bool is_zero() const;// p (p > 0) is the number of digits after the decimal pointstd::string to_string(int p) const;long 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, long double x);friend Decimal operator + (long 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, long double x);friend Decimal operator - (long 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 += (long double x);Decimal & operator += (const Decimal &b);Decimal & operator -= (int x);Decimal & operator -= (long long x);Decimal & operator -= (long 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 calledfriend Decimal operator * (const Decimal &a, long double x);friend Decimal operator * (long double x, const Decimal &a);friend Decimal operator / (const Decimal &a, long double x);Decimal & operator *= (long double x);Decimal & operator /= (long 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(long 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 signwhile (*s != 0) {if (*s == '-') {is_neg = true;++s;break;} else if (*s >= 48 && *s <= 57) {break;}++s;}// read the integer partwhile (*s >= 48 && *s <= 57) {integer = integer * 10 + *s - 48;++s;}// read the decimal partif (*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; }long double Decimal::to_double() const {long double ret = integer;long 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 >= 0if (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 <= 0if (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 >= 0if (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 <= 0if (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 >= 0if (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 <= 0if (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 >= 0if (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 <= 0if (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 = 0if (!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| - breturn -(-a + b);} else {// a - -|b|return a + -b;} }Decimal operator + (const Decimal &a, long double x) {return a + Decimal(x); }Decimal operator + (long double x, const Decimal &a) {return Decimal(x) + a; }Decimal operator - (const Decimal &a, long double x) {return a - Decimal(x); }Decimal operator - (long double x, const Decimal &a) {return Decimal(x) - a; }Decimal & Decimal::operator += (long double x) {*this = *this + Decimal(x);return *this; }Decimal & Decimal::operator -= (long 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; }// ---------- decimal lib end ---------- inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } #include <algorithm> #include <iostream> #define MAXN 8005 using namespace std; int s[MAXN],tot; long double f[2][MAXN]; short key[MAXN][MAXN]; int q[MAXN],head,tail; inline long double calc(int n,int i,int t){return (s[n]-s[i]+f[t^1][i])/(n-i+1);} inline bool cmp(int i,int j,int k,int t){return (s[i]-f[t^1][i]-s[j]+f[t^1][j])*(i-k)<(s[i]-f[t^1][i]-s[k]+f[t^1][k])*(i-j);} Decimal getans(int k,int n) {if (!k) return s[1];return (s[n]-s[key[k][n]]+getans(k-1,key[k][n]))/(n-key[k][n]+1); } long double ans=0; int pos; int main() {int n,k,p;n=read(),k=read(),p=read();s[tot=1]=read();for (int i=1;i<n;i++){int t=read();if (t>s[1]) s[++tot]=t;}n=tot;sort(s+1,s+n+1);if (k>=n) k=n-1;for (int i=1;i<=n;i++) s[i]+=s[i-1],f[0][i]=s[1];f[1][1]=s[1];for (int i=1,t=1;i<=k;i++,t^=1){head=1,tail=1;q[1]=1;for (int j=2;j<=n;j++){while (head<tail&&calc(j,q[head],t)<calc(j,q[head+1],t)) ++head;f[t][j]=calc(j,key[i][j]=q[head],t);while (head<tail&&cmp(j,q[tail],q[tail-1],t)) --tail;q[++tail]=j;}}cout<<getans(k,n).to_string(2*p);return 0; }

總結

以上是生活随笔為你收集整理的【NOI2016】国王饮水记【贪心】【斜率优化】【决策单调性】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。