牛客多校4 A

Task Computing

题目链接

题目大意

给出一个长度为\(n\)的数组，要求选\(m\)个数，并任意排序，最大化\(\sum_{i=1}^mw_{ai}*\prod_{j=0}^{i-1}p_{aj}\)，每个物品价值为\(w_i\)

题解

我们将这个贡献的式子展开，\(原式=w_{a_1}*p_{a_0}+w_{a_2}*p_{a_0}*p_{a_1}+w_{a_3}*p_{a_0}*p_{a_1}*p_{a_2}...\)，从前往后填贡献是这样计算的，那我们换一个方向呢？以前三项为例，计算顺序就变成了\(((w_{a_3}*p_{a_2}+w_{a_2})*p_{a_1}+w_{a_1})*p_{a_0}\)，可以发现，若当前贡献是\(pre\)，则每次贡献变化都是先乘上\(w\)，再加上\(p\)，于是我们就可以试着写一下cmp函数，对于\(x,y\)，再从后往前填数的情况向下，想让x优先于y被选择应该满足什么条件呢? $$ w_x+p_x(w_y+p_y\times pre)>w_y+p_y(w_x+p_x\times pre) $$

\[ w_x+p_xw_y>w_y+p_yw_x \]

\[ 分离x和y\ \ \ \ \frac{w_x}{1-p_x}>\frac{w_y}{1-p_y} \]

有了排序函数后，就可以通过DP求解了，这里可以将cmp函数反一下，让dp更好写

令\(f[i,j]\)表示考虑前\(i\)个数取\(j\)的情况中贡献的最大值

• \(f[i,j]=max(f[i-1,j],f[i-1,j-1]*p_i+w_i\)

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
struct Node
{
    double w;
    double p;
    bool operator < (const Node &t) const
    {
        return w + p * t.w < t.w + t.p * w;
    }
}a[N];
int n, m;
double f[N][25];
void solve() 
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> a[i].w;
    for (int i = 1; i <= n; i ++) 
    {
        cin >> a[i].p;
        a[i].p /= 10000;
    }        
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n ; i ++ ) 
    {
        for (int j = 1; j <= min(i, m); j ++) 
        {
            f[i][j] = max(f[i - 1][j], a[i].w + a[i].p * f[i - 1][j - 1]);
        }
    }
    printf("%.12lf\n", f[n][m]);
}

int main()
{
    int T = 1;
    // cin >> T;
    while(T -- ) solve();
    return 0;
}