[dp]Task Computing 2022牛客多校第4场 A

题目描述

See Problem N for PDF statements.

As it says, Time is Money, Efficiency is Life. A client has a computing task waiting for uploading to the cloud servers. However, due to the resource limits and many other tasks, a task usually cannot be worked on a single server but multiple servers, one after another. You, as an employee of a cloud server provider who specializes in task allocation, need to select several servers from a limited number of cloud servers to perform calculations. We know that even the same servers will perform differently in different environments.

There are nnn cloud servers available in the vicinity of the client's region numbered from 111 to nnn. The iii-th cloud server has two parameters: wiw_iwi​ and pip_ipi​, which indicate the computing power and transmission efficiency of that server, respectively. The supervisor requires that each task must be computed by exactly mmm of these servers. The client's computational task is not parallelizable, so you must sequence the work of the mmm servers to maximize the total computational efficiency. We define the total computational efficiency as follows:

∑i=1mwai∏j=0i−1paj\sum\limits_{i=1}^{m}w_{a_i}\prod\limits_{j=0}^{i-1}p_{a_j}i=1∑m​wai​​j=0∏i−1​paj​​

where a1,a2,…,ama_1,a_2,\ldots, a_ma1​,a2​,…,am​ (pairwise distinct, 1≤ai≤n1\le a_i \le n1≤ai​≤n) are the servers you selected. For convenience, a0=0,p0=1a_0 = 0, p_0 = 1a0​=0,p0​=1.

输入描述:

The first line contains two integers n,mn,mn,m (1≤n≤1051\le n\le 10^51≤n≤105, 1≤m≤min⁡(n,20)1\le m \le \min(n,20)1≤m≤min(n,20)), denoting the number of cloud servers and servers that you have to select.

The second line contains nnn integers w1,w2,…,wnw_1,w_2,\ldots, w_nw1​,w2​,…,wn​ (1≤wi≤1091\le w_i \le 10^91≤wi​≤109), denoting the servers' computing power.

The third line contains nnn integers q1,q2,…,qnq_1,q_2,\ldots, q_nq1​,q2​,…,qn​ (8000≤qi≤120008000\le q_i \le 120008000≤qi​≤12000), where pi=qi10000p_i = \frac{q_i}{10000}pi​=10000qi​​ denotes the iii-th server's transmission efficiency.

输出描述:

Output a float number denoting the maximal total computational efficiency. Your answer is considered correct if the relative or absolute error between yours and the standard solution is not greater than 10−610^{-6}10−6.

示例1

输入

5 2
1 2 3 4 5
12000 11000 10000 9000 8000

输出

8.5000000000000000

题意： 给出n个任务，要求从其中挑选出m个任务，其中第i个任务的贡献为wi*前面i-1个任务的p值乘积，求最大贡献。

分析： 可以发现m个任务的顺序不同那么最终贡献不同，所以首先需要确定一个最优的顺序，这个顺序可以通过比较交换相邻两项后的贡献差来确定，根据下图的推导过程可以得到贡献差：

之后就可以根据贡献差来sort了，sort后得到的新序列中任意两位置交换一定不会更优，所以只需要在该序列中找到一个长度为m的子序列使其贡献最大，这个过程可以通过dp来实现，一开始想的状态是dp[i][j]表示前i个数中选j个得到的最大贡献，但是这样设状态的话当前状态不能通过上一个状态转移过来，也就是dp[i][j]不一定是通过dp[i-1][j-1]得到的，因为dp[i][j]的值还需要加上一个连乘，很可能加上这个连乘后之前某个状态就比上个状态更优了，所以这道题目不能这么做。

正确的做法是设dp[i][j]表示第i个到第n个任务中选择j个任务得到的最大贡献，这样显然是可以递推得到dp[i][j]的值，也就是dp[i][j] = dp[i+1][j-1]*p[i]+w[i]，不得不说这种构造方法还是很巧妙的！

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#define pii pair
#define w first
#define p second
using namespace std;
 
pii a[100005];
double dp[100005][25];//dp[i][j]表示从第i个任务到第n个任务中选j个的最大贡献 
 
bool cmp(pii x, pii y){
	return x.w*(1-y.p)+y.w*(x.p-1) > 0;
}
 
signed main()
{
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i].w);
	for(int i = 1; i <= n; i++){
		scanf("%lf", &a[i].p);
		a[i].p /= 1e4;
	}
	sort(a+1, a+n+1, cmp);
	dp[n][1] = a[n].w;
	for(int i = n-1; i >= 1; i--){
		for(int j = 0; j <= m; j++){
			//不选
			dp[i][j] = dp[i+1][j];
			//选
			if(j >= 1 && dp[i][j] < dp[i+1][j-1]*a[i].p+a[i].w)
				dp[i][j] = dp[i+1][j-1]*a[i].p+a[i].w;
		}
	}
	double ans = 0.0;
	printf("%.10f\n", dp[1][m]);
    return 0;
}