牛客多校4 A.Task Computing 思维

A

题意

$n(n\le 1e5)$ 个物品，每个物品有 $w_i,p_i$ ，现从中取出 $m(m\le 20)$ 件，最大化

思路

这种题一般都是通过比较交换相邻两项后对答案的贡献，得出一种排序方法，排序之后计算即可。
假设现在选了 $k$ 件物品，这个式子其实就是 $Sum=w_1+w_2\ast (p_1)+w_3\ast (p_1{p}_2)+...+w_k\ast (p_1{p}_2...p_{k-1})$ 。考虑如果再选一件$(w_0,p_0)$ 放在最前面，则 $Sum=w_0+p_o\ast Sum$ 。推导如图。之后排序即可。

代码

struct Node {
    
	double w, p;
	bool operator < (const Node &x) const {
    
		return w * (1 - x.p) > x.w * (1 - p);
	}
}node[maxn];
int n, m;
double f[maxn][25];	//i-n中选j个最大值
void solve() {
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
    
    	cin >> node[i].w;
    }
    for(int i = 1; i <= n; i++) {
    
    	cin >> node[i].p;
    	node[i].p /= 10000;
    }
    sort(node + 1, node + n + 1);
    for(int i = 1; i <= n; i++) {
    
    	for(int j = 0; j <= m; j++) f[i][j] = -INF;
    }
    f[n + 1][0] = 0;
    for(int i = n; i >= 1; i--) {
    
    	for(int j = 0; j <= m; j++) {
    
    		f[i][j] = f[i+1][j];
    		if(j)
	    		f[i][j] = max(f[i+1][j], f[i+1][j-1] * node[i].p + node[i].w);
    	}
    }
    cout << f[1][m] << endl;
}