【补题日记】[2022牛客暑期多校4]A-Task Computing

Pro

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

Sol

先看m=2的情况，容易列出两个式子：$w_1+w_2\times p_1$和$w_2+w_1\times p_2$，假设前者更大，即1在2的前面，化简式子为：

$\frac{p_2-1}{w_2}\le \frac{p_1-1}{w_1}$，但其实不化出这个式子来也没问题，因为为了避免精度问题写重载的时候还要乘回来哈哈哈。

然后就是一个证明（或者说瞎猜）这个结论可以推广到$m>2$的情况

贪心按照这个方法排序之后，就可以考虑dp的问题了

通过对题目中给的式子提取公因式可以得到

$$原式=w_1+p_1\times (w_2+p_2\times (w_3+...))$$

因此通过逆序可以得到状态转移方程为 f i , j = m a x { f i + 1 , j , f i + 1 , j − 1 × p i + w i } f_{i,j}=max\{f_{i+1,j},f_{i+1,j-1}\times p_i+w_i\} fi,j​=max{fi+1,j​,fi+1,j−1​×pi​+wi​}

是不是有点像01背包了

Code

//By cls1277
#include
using namespace std;
typedef long long LL;
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define endl '\n'

const LL maxn = 1e5+5;
LL n, m;
double f[maxn][25];

struct Node {
    LL w;
    double p;
}a[maxn];

bool operator < (const Node &x, const Node &y) {
    return (x.w+y.w*x.p>=y.w+x.w*y.p);
}

inline LL read() {
	LL x = 0, f = 1;char c = getchar();
	while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
	return x * f;
}

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr);
    #ifdef DEBUG
    freopen("data.txt","r",stdin);
    #endif
    n=read(); m=read(); // cin>>n>>m;
    Fo(i,1,n) a[i].w=read(); //cin>>a[i].w;
    Fo(i,1,n) {
        LL x; x=read(); //cin>>x;
        a[i].p = x*1.0/10000;
    }
    sort(a+1, a+n+1);
    Ro(i,n,1) {
        Fo(j,1,m) {
            f[i][j] = max(f[i+1][j], f[i+1][j-1]*a[i].p+a[i].w);
        }
    }
    printf("%.16lf",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
42
43
44
45
46
47
48
49
50
51