【NOI2016】国王饮水记【贪心】【斜率优化】【决策单调性】
傳送門
首先比h1h_1h1?小的肯定沒用,直接無視
然后考慮合并的順序
①在無限制的情況下,合并多個不如一個一個合并
a<b<ca<b<ca<b<c時,a+b2+c2>a+b+c3{{a+b \over 2}+c\over 2}>{{a+b+c}\over 3}22a+b?+c?>3a+b+c?
②先合并小的比先合并大的優
整理一下,就是把>h1> h_1>h1?的從小到大排序,然后每次把當前的和序列中靠前的若干個合并
顯然是個斜率優化的模型
設fk,nf_{k,n}fk,n?表示前nnn個合并kkk次的最大值
fk,n=max?1≤i<nfi+Sn?Sin?i+1f_{k,n}=\max_{1\leq i<n}\frac{f_i+S_n-S_i}{n-i+1}fk,n?=1≤i<nmax?n?i+1fi?+Sn??Si??
推一下式子發現很惡心
但注意到這個式子本身就是斜率的形式
可以看成所有(i?1,Si?fi)(i-1,S_i-f_i)(i?1,Si??fi?)到(n,Sn)(n,S_n)(n,Sn?)的最大斜率
意識流一波,維護一個下凸殼,每次最優決策是過(n,Sn)(n,S_n)(n,Sn?)的一條與凸殼切于端點的直線,可以三分一下……
注意到hhh嚴格單調增,所以(n,Sn)(n,S_n)(n,Sn?)本身就組成了下凸殼
對于兩個決策k1,k2k_1,k_2k1?,k2?,設iii是k2k_2k2?優于k1k_1k1?的(i,Si)(i,S_i)(i,Si?),即(k1?1,Sk1?fk1),(k2?1,Sk2?fk2),(i,Si)(k_1-1,S_{k_1}-f_{k_1}),(k_2-1,S_{k_2}-f_{k_2}),(i,S_i)(k1??1,Sk1???fk1??),(k2??1,Sk2???fk2??),(i,Si?)往上翹
如圖,ki?1,i>kk2,ik_{i-1,i}>k_{k_2,i}ki?1,i?>kk2?,i?,又因為ki,i+1>ki?1,ik_{i,i+1}>k_{i-1,i}ki,i+1?>ki?1,i?,所以對于i+1i+1i+1 k2k_2k2?仍然更優
所以可以把k1k_1k1?彈掉
這樣可以做到O(nkp)O(nkp)O(nkp) 這里因為最多只能取n?1n-1n?1次合并,所以n,kn,kn,k是同階的
然后可以用低精度算dpdpdp并記錄決策,最后用高精度算一次 復雜度O(nk+np)O(nk+np)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】国王饮水记【贪心】【斜率优化】【决策单调性】的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 鸿业负荷计算9.0打不开闪退完美解决方法
- 下一篇: 【NOI2012】骑行川藏【拉格朗日乘数