CF167B Wizards and Huge Prize

题意：
  你要去 \(n(n\leq200)\) 个地点比赛，顺序自定。获胜奖品有的是一个奖杯，有的是一个容量为 \(b_i\) 的装奖杯的书包。开始时你有一个容量为 \(k\) 的书包。每场比赛的获胜概率为 \(p_i\) 。问你至少赢 \(l\) 场且所有奖杯都被装入书包的概率为多少。

思路：
  其实是有一个相对简单的方法的。就是由于顺序自定，那肯定优先去奖品为书包的地方比赛。先排序把送书包的放在前面，然后 \(dp[i][j][k]\) 表示前 \(i\) 天赢了 \(j\) 把，剩余空间为 \(k\) 就ok了。再者 \(n\leq200\)，故 \(k\) 只要计算 \(200\) 以内就好。   但是开始没想到这个三维DP的做法，而是用了二维DP。思路比较巧妙虽然WA了6发。 \(dp[i][j]\) 代表送包的比赛赢了 \(i\) 把，空余位置 \(j\) 个。 \(win[i]\) 代表不送包的比赛赢了 \(i\) 局的概率。   最关键的是两者怎么实现综合考虑。送包的比赛赢了 \(i\) 局以后，不送包的比赛至少需要赢 \(max(0,l-i)\) 局，但又最多赢 \(j\) 局。同时，\(win\) 的前缀和到底要用哪一段也要考虑清楚。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 220;
double dp[maxn][40220], win[40220], pre[40220], ans;
struct Node
{
    double pct;
    int cap;
    bool operator<(const Node &x)
    {
        return cap < x.cap;
    }
}p[maxn];
int n, l, k, nc, tot;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}

inline void readin()
{
    n = read(), l = read(), k = read();
    tot += k;
    for (int i = 1; i <= n; ++i)
        p[i].pct = 1.0 * read() / 100;
    for (int i = 1; i <= n; ++i)
        p[i].cap = read(), tot += p[i].cap == -1 ? 0 : p[i].cap;
    sort(p + 1, p + 1 + n);
    nc = n;
    for (int i = 1; i <= n; ++i)
        if (p[i].cap != -1)
        {
            nc = i - 1;
            break;
        }
}

inline void run()
{
    dp[0][k] = 1;
    win[0] = 1;
    for (int i = 1; i <= nc; ++i)
        for (int j = i; j > 0; --j)
        {
            double tent = 1.0 * win[j - 1] * p[i].pct;
            win[j] += tent;
            win[j - 1] -= tent;
        }
    pre[0] = win[0];
    for (int i = 1; i <= tot; ++i)
        pre[i] = pre[i - 1] + win[i];
    for (int i = nc + 1; i <= n; ++i)
        for (int j = i; j > nc; --j)
            for (int q = tot; q >= p[i].cap; --q)
                if (dp[j - 1 - nc][q - p[i].cap])
                {
                    double tent = 1.0 * dp[j - 1 - nc][q - p[i].cap] * p[i].pct;
                    dp[j - nc][q] += tent;
                    dp[j - 1 - nc][q - p[i].cap] -= tent;
                }
    for (int i = 0; i <= n - nc; ++i) //最关键的地方
    {
        int tent = i >= l ? 0 : l - i;
        for (int j = tent; j <= tot; ++j)
            if (tent)
                ans += 1.0 * dp[i][j] * (pre[j] - pre[tent - 1]);
            else
                ans += 1.0 * dp[i][j] * pre[j];
    }
}

int main()
{
    readin();
    run();
    printf("%.12lf\n", ans);
    return 0;
}