Description

有\(n\)个数，最多\(k\)次操作，每次可选择一些数，使得它们全都变成它们的平均数

最大化第一个数的值

保留\(p\)位小数

\(n\leq 8000,p\leq3000\)

Solution 

因为对精度的要求，套用高精度小数类的话，单次计算为\(O(p)\)

因此我们动规的过程中，采用记录决策点，并用long double记录\(F\)数组的值，最后在进行计算答案

根据结论，最后的方案一定是按照从小到大的顺序依次合并比\(h_1\)大的数，每次操作的包含\(h_1\)

将原数组(只考虑比\(h_1\)大的那些数字)

设\(a_i=\sum_{j=1}^{i}h_i\)

考虑\(dp\)转移

\[ f_{k,i}=Max[\frac{a_i-(a_j-f_{k-1,j})}{i-(j-1)}] \]

所以相当于求\((i,a_i)\)与所有\((j-1,a_j-f_{k-1,j})\)的最大斜率

显然这样的点一定会在\((j-1,a_j-f_{k-1,j})\)的下凸壳上

然后这个显然满足决策单调性

因为设\(A(i+1,a_i+h_{i+1})\)，\(B(i,a_i)\)，\(B\)的决策点是\(P(j-1,a_j-f_j)\)，根据\(h_i\)按照从小到大的顺序排列，显然有\(k_{AP}>k_{BP}\)，那么\(AP\)就与这个下凸壳相交，需要将决策点右移

最后，发现每次选的数的数量都不大于上一次，否则，将最小的改为上一次合并一定更加优秀

然后也不知道怎么证明的，大于\(1\)的段不超过\(14\)段，所以只要\(dp\)出前\(14\)层就可以了

Code 

#include
    
     #define ll long long#define ld long double#define reg register#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))// ---------- decimal lib start ----------const int PREC = 3005;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;}// ---------- decimal lib end ----------inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}int n,k,p;const int MN=10005;ll a[MN],_1;int from[20][MN];ld f[20][MN];Decimal ans;struct Point{    ld x,y;    Point(ld _a=0,ld _b=0):x(_a),y(_b){}    ld sl(const Point&o){return (ld)(o.y-y)/(ld)(o.x-x);}};class xxx{    Point st[MN];    int hd,tl;    public:    void init(){hd=tl=1;st[1]=Point(-1,(ld)(-_1));}    void get(int K,int i)    {        Point cur=Point((ld)i,(ld)a[i]);        while(hd
     
      st[hd].sl(cur))++hd;        from[K][i]=(int)st[hd].x+1.;        f[K][i]=st[hd].sl(cur);    }    void ins(int K,int j)    {        Point cur=Point((ld)j-1,(ld)(a[j]-f[K][j]));        while(hd
      
       st[tl].sl(cur))--tl;        st[++tl]=cur;    }}que;void cal(int x,int step){    if(!x||!step)return;    cal(from[step][x],step-1);    ans=(ans+(a[x]-a[from[step][x]]))/(x-from[step][x]+1);}int main(){    n=read()-1;k=read();p=read();_1=read();    k=min(k,n);    reg int i,K,tot=0;    for(i=1;i<=n;++i)    {        a[++tot]=read();        if(a[tot]<=_1) --tot;    }    n=tot;if(n==0)    {        ans=Decimal(_1);        std::cout<
       
        <
       
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！