[Supplementary Questions Diary] [2022 Niu Ke Summer Multi-School 4] A-Task Computing

Pro

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

Sol

先看m=2的情况,It is easy to list two equations：$w_1+w_2\times p_1$和$w_2+w_1\times p_2$,Suppose the former is larger,即1在2的前面,The simplified formula is ：

$\frac{p_2-1}{w_2}\le \frac{p_1-1}{w_1}$,But in fact, it is not a problem to not come out of this formula,Because in order to avoid precision problems, it has to be multiplied back when writing overloads.

Then there is a proof（or guessing）This conclusion can be extended to$m>2$的情况

After greedy sorting according to this method,就可以考虑dp的问题了

It can be obtained by extracting the common factor of the formula given in the question

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

Therefore, the state transition equation can be obtained by reversing the order$f_{i,j}=max\{f_{i+1,j},f_{i+1,j-1}\times p_i+w_i\}$

是不是有点像01背包了

Code

//By cls1277
#include<bits/stdc++.h>
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;
}