题目大意

​ 从n个任务中选 mm 个(a1,a2,,,am)(a1,a2,,,am)出来并任意排序，收益是 ∑i=1mwai∏ji−1paj\sum_{i=1}^mw_{a_i}\prod_{j}^{i-1}p_{a_j}，求最大收益

分析

考虑一种排序方案使得按此方案可以计算出最大收益

考虑 axa_x 放在 aya_y 前收益更高的条件

分析

按照 wx−wx∗py>wy−wy∗pxw_x - w_x*p_y > w_y - w_y*p_x 排序 ，这样 x 在 y 前一定更优

m<=20m <=20，做背包

f[i][j]f[i][j] 为 考虑 [i −n][i \ - n] ,取了 jj 个 的最大价值

注意为何从后往前

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int n,m;
struct node{
    int w;
    double q;
    bool operator<(const node&t) const{
        return w-w*t.q > t.w - t.w * q;
    }
}a[100005];

double f[100005][21];

signed main()
{
    cin>>n>>m;

    for(int i = 1;i <= n;i++) cin >> a[i].w;
    for(int i = 1;i <= n;i++) cin >> a[i].q,a[i].q /= 10000.0;

    sort(a+1,a+1+n);
    for(int i = n;i>=1;i--)
        for(int j = 1;j <= m;j++){
            f[i][j] = max(f[i+1][j],f[i+1][j-1]*a[i].q+a[i].w);
        }
    printf("%.6f\n",f[1][m]);
    return 0;
}