传送门

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<bits/stdc++.h>
#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<tl&&st[hd+1].sl(cur)>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<tl&&st[tl-1].sl(st[tl])>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<<ans.to_string(p+3)<<std::endl;
        return 0;
    }
    std::sort(a+1,a+n+1);
    f[0][0]=_1;int lim=min(14,k);
    for(i=1;i<=n;++i) a[i]+=a[i-1],f[0][i]=_1;
    for(K=1;K<=lim;++K)
    {
        f[K][0]=_1;que.init();
        for(i=1;i<=n;++i)
            que.get(K,i),que.ins(K-1,i);
    }
    
    ans=Decimal(_1);cal(n-(k-lim),lim);
    for(i=n-(k-lim)+1;i<=n;++i) ans=(ans+a[i]-a[i-1])/2;
    std::cout<<ans.to_string(p+2)<<std::endl;
    return 0;
}

---

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