22牛客多校4 - Task Computing（相邻贪心，推式子倒序DP）
https://ac.nowcoder.com/acm/contest/33189/A
题意
给定长度为 n 的数组
a
[
]
a[]
a[]，每个位置有两个元素
w
i
,
p
i
w_i,\ p_i
wi, pi。
从中按照任意顺序选出若干个位置 a 1 , a 2 , … , a m ( 1 ≤ a i ≤ n ) a_1, a_2, \ldots, a_m \text (1 \leq a_i \leq n \text ) a1,a2,…,am(1≤ai≤n) ，使得： ∑ i = 1 m w a i ∏ j = 0 i − 1 p a j \sum_{i=1}^m w_{a i} \prod_{j=0}^{i-1} p_{a_j} ∑i=1mwai∏j=0i−1paj 最大。
输出最大值。
1
≤
n
≤
1
0
5
,
1
≤
m
≤
min
(
n
,
20
)
1≤n≤10^5,\ 1\le m \le \min(n,20)
1≤n≤105, 1≤m≤min(n,20)
1
≤
w
i
≤
1
0
9
,
8000
≤
q
i
≤
12000
,
p
i
=
10000
q
i
1\le w_i \le 10^9,\ 8000≤q_i≤12000,\ p_i= \frac {10000} {q_i}
1≤wi≤109, 8000≤qi≤12000, pi=qi10000
思路
首先可以将数组重新排序，然后只需要按照从前往后的顺序挑选若干个位置，使得
a
1
,
a
2
,
…
,
a
m
(
1
≤
a
i
≤
n
)
a_1, a_2, \ldots, a_m \text (1 \leq a_i \leq n \text )
a1,a2,…,am(1≤ai≤n) 最大。
相邻的两项互换位置对其余位置没有影响，而如果交换之后能使结果更优的话就交换，最终能够得到最佳的排列顺序。
只考虑 3 个位置，然后交换后两个位置，比较两个交换之后的答案，得出：如果
w
1
+
w
2
∗
p
1
>
w
2
+
w
1
∗
p
2
w_1 + w_2*p_1 > w_2 + w_1*p_2
w1+w2∗p1>w2+w1∗p2 时，1 位置放到 2 位置前面更优。按照这个原则将所有位置排序。
然后就是从这 n 个位置中，从前往后依次挑出 m 个位置，使得 a 1 , a 2 , … , a m ( 1 ≤ a i ≤ n ) a_1, a_2, \ldots, a_m \text (1 \leq a_i \leq n \text ) a1,a2,…,am(1≤ai≤n) 最大。
考虑 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 + w_2p_1 + w_3p_1p_2 + w_4p_1p_2p_3
w1+w2p1+w3p1p2+w4p1p2p3
=
w
1
+
p
1
(
w
2
+
w
3
p
2
+
w
4
p
2
p
3
)
=w_1 + p_1(w_2 + w_3p_2+w_4p_2p_3)
=w1+p1(w2+w3p2+w4p2p3)
=
w
1
+
p
1
[
w
2
+
p
2
(
w
3
+
p
3
w
4
)
]
=w_1 + p_1[w_2 + p_2(w_3 + p_3w_4)]
=w1+p1[w2+p2(w3+p3w4)]
容易发现，可以从后往前递推： w i + p i ∗ a n s w_i + p_i*ans wi+pi∗ans， a n s 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<bits/stdc++.h>
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;
}
还需要注意的是，题目给出的
p
i
p_i
pi 是乘以 10000 之后的，一开始先没有除以 10000，觉得乘以 10000 对排序没有影响，想着最后转移的时候再除，减少精度误差，其实这样是对排序有影响的，排序是按照 wi + wj*pi 的，还加上一个值，等式两边不能同时约去 10000，会出现错误！
所以要先提前除过来。