题目概述

有 $n$ 个物品，可以用两种方式获得（可以一起用，一种获得了即可），两种方式成功的概率分别为 $a_i,b_i$ ，第一种方式可以用 $A$ 次，第二种方式可以用 $B$ 次。问获得物品的期望的最大值。

解题报告

神坑-1。很明显可以 $f_{i,j,k}$ 表示前 $i$ 个物品第一种方法用了 $j$ 次第二种方法用了 $k$ 次的最优解，但是这样是 $O(n^3)$ 的，要想办法优化。

转移和转移数都是 $O(1)$ 的，只能优化状态数了，于是想到wqs二分。因为用了越多收益越来越少（容易抓的都先用掉了），并且用越多越好，所以没毛病。砍掉一维之后变成 $O(n^2log_2n)$ ，可以过。

由于校内比赛时候出了这道题的加强版，所以继续想发现其实两维都可以砍掉，于是很愉快的做到 $O(nlog_2^2n)$ 。

示例程序

切记最后加上的一定是乘 $A$ 和乘 $B$ ！

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
using namespace std;
typedef long double DB;
const int maxn=100000;

int n,A,B;DB a[maxn+5],b[maxn+5],f[maxn+5];pair<int,int> g[maxn+5];

inline void Fix(int i,DB F,int a,int b) {if (F>f[i]) f[i]=F,g[i].fr=a,g[i].sc=b;}
inline void DP(DB M,DB m){
    for (int i=1;i<=n;i++){
        f[i]=f[i-1];g[i]=g[i-1];
        Fix(i,f[i-1]+a[i]-M,g[i-1].fr+1,g[i-1].sc);
        Fix(i,f[i-1]+b[i]-m,g[i-1].fr,g[i-1].sc+1);
        Fix(i,f[i-1]+1-(1-a[i])*(1-b[i])-M-m,g[i-1].fr+1,g[i-1].sc+1);
    }
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    while (~scanf("%d%d%d",&n,&A,&B)){
        for (int i=1;i<=n;i++) {double x;scanf("%lf",&x);a[i]=x;}
        for (int i=1;i<=n;i++) {double x;scanf("%lf",&x);b[i]=x;}
        DB L=0,R=1,l,r;
        for (DB M=(L+R)/2;R-L>1e-8;M=(L+R)/2){
            l=0;r=1;for (DB m=(l+r)/2;r-l>1e-8;m=(l+r)/2) DP(M,m),g[n].sc<=B?r=m:l=m;
            DP(M,r);g[n].fr<=A?R=M:L=M;
        }DP(R,r);printf("%.6f\n",double(f[n]+R*A+r*B));
    }return 0;
}