22牛客多校4 - Task Computing（相邻贪心，推式子倒序DP）

https://ac.nowcoder.com/acm/contest/33189/A

题意
给定长度为 n 的数组 $a[]$，每个位置有两个元素 $w_i,p_i$。

从中按照任意顺序选出若干个位置 $a_1,a_2,\dots ,a_m\text{(}1\le a_i\le n\text{)}$ ，使得：${\sum }_{i=1}^m{w}_{ai}{\prod }_{j=0}^{i-1}{p}_{a_j}$ 最大。

输出最大值。

$1\le n\le 10^5,1\le m\le \min (n,20)$
$1\le w_i\le 10^9,8000\le q_i\le 12000,p_i=\frac{10000}{q_i}$

思路
首先可以将数组重新排序，然后只需要按照从前往后的顺序挑选若干个位置，使得 $a_1,a_2,\dots ,a_m\text{(}1\le a_i\le n\text{)}$ 最大。
相邻的两项互换位置对其余位置没有影响，而如果交换之后能使结果更优的话就交换，最终能够得到最佳的排列顺序。
只考虑 3 个位置，然后交换后两个位置，比较两个交换之后的答案，得出：如果 $w_1+w_2\ast p_1>w_2+w_1\ast p_2$ 时，1 位置放到 2 位置前面更优。按照这个原则将所有位置排序。

然后就是从这 n 个位置中，从前往后依次挑出 m 个位置，使得 $a_1,a_2,\dots ,a_m\text{(}1\le a_i\le n\text{)}$ 最大。

考虑 DP。
一开始可能会这样想：定义 f[i, j] 表示，从前 i 个位置中选出 j 个位置，所得出的结果最大值。
从当前位置选和不选两种状态来转移，如果不选就是 f[i-1, j]，如果选便是从 f[i-1, j-1] 转移，同时加上 wi 乘上 f[i-1, j-1] 时 pi 的乘积，所以还要维护出 mul[i, j]，表示到达 (i, j) 状态时的 pi 乘积。这样就可以转移了。
但是这样转移是否是正确的呢？
不一定，f[i-1, j-1] 得出的答案是最大的，但是得到这种状态时 pi 的乘积却可能是很小的，那么转移过来的答案和乘积有关系，所以从上个位置的最值转移不一定是最优的。不能这样转移。

没有办法，再化化式子。
如果选了 1，2，3，4 位置，那么最终的答案为：
$w_1+w_2{p}_1+w_3{p}_1{p}_2+w_4{p}_1{p}_2{p}_3$
$=w_1+p_1(w_2+w_3{p}_2+w_4{p}_2{p}_3)$
$=w_1+p_1[w_2+p_2(w_3+p_3{w}_4)]$

容易发现，可以从后往前递推：$w_i+p_i\ast ans$，$ans$ 为后一位置递推的答案。

所以可以从后往前 DP。
f[i, j] 表示，从 i 位置到 n 位置中选出 j 个位置，答案的最大值。
f[i, j] = max(f[i+1, j], wi + pi*f[i+1, j-1])。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long
#define endl '\n'

const int N = 200010, mod = 1e9+7;
int T, n, m;
struct node{
	int w;
	double p;
}a[N];
double f[N][21];

bool cmp(node a, node b){
	return a.w + b.w*a.p > b.w + a.w*b.p;
}

signed main(){
	Ios;
	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 = a[i].p/10000;
	}
	
	sort(a+1, a+n+1, cmp);
	
	for(int i=n;i>=1;i--)
	{
		for(int j=1;j<=min(n-i+1, m);j++)
		{
			f[i][j] = max(f[i+1][j], a[i].w + a[i].p * f[i+1][j-1]);
		}
	}
	printf("%.10f", f[1][m]);
	
	return 0;
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

还需要注意的是，题目给出的 $p_i$ 是乘以 10000 之后的，一开始先没有除以 10000，觉得乘以 10000 对排序没有影响，想着最后转移的时候再除，减少精度误差，其实这样是对排序有影响的，排序是按照 wi + wj*pi 的，还加上一个值，等式两边不能同时约去 10000，会出现错误！
所以要先提前除过来。