CF167B
题意
给定初始背包容量 \(k\), 要进行 \(n\) 场比赛，每场比赛有 \(p_i\%\) 的概率能够胜利，赢的一场比赛能获得一个奖励——当 \(a_i = -1\) 时获得一个体积为 \(1\) 的奖品，或者当 \(a_i > 0\) 时给背包增加 \(a_i\) 容量，求所有比赛结束后至少赢得 \(l\) 场且背包能装下所有奖品的概率。
(\(1 \le n \le 200, 0 \le l, k, a_i \le 200, 0 \le p_i \le 100\))
解析
大部分题解都把奖品和增加背包容量放在一起进行转移，其实两者可以分开，我们将能增加背包容量的比赛（以下简称a类比赛）设为 \(a_i\)，其它的比赛（以下简称b类比赛）设为 \(b_i\)。对于背包容量的转移，设 \(i\) 为当前进行了几场a类比赛（此处转移方程均针对a类比赛），\(j\) 为已赢下几场比赛，\(k\) 为背包容量，有转移方程如下：
\[dp^1_{i, j, k} = dp^1_{i - 1, j, k} \times \frac{100 - p_i}{100} + dp^1_{i - 1, j - 1, k - a_i} \times \frac{p_i}{100} \]初始化为 \(dp^1_{1,0,k} = 1\)。但此时复杂度为 \(O(n^2\sum{a_i})\)，约 \(1.6 \times 10^9\)，肯定系T飞了的。
观察到背包容量其实最多只需要到 \(n\)，更多的容量没有作用，因此可以将第三维（\(k\) 的那一维）的范围从 \(\sum{a_i}\) 压缩到 \(n\)，大概 \(200\)，这样时间复杂度就能过了；另外，对于dp1数组的第一维（\(i\) 的一维），可以滚动数组优化掉，使空间复杂度从 \(O(n^3)\) 压到 \(O(n^2)\)，不至于空间超限。
而对于b类比赛的转移，由于奖品体积固定为 \(1\)，设 \(i\) 为第几场b类比赛，\(j\) 为已赢下b类比赛的数量，有转移方程：
\[dp^2_{i, j} = dp^2_{i - 1, j} \times \frac{100 - p_i}{100} + dp^2_{i - 1, j - 1} \times \frac{p_i}{100} \]同样的，dp2数组的第一维也是可以滚动数组优化掉的。
最后，先对dp1数组进行前缀和处理，即可求出答案 \(ans\)，设共有 \(m\) 场b类比赛，答案为
\[ans = \sum{dp^2_{m, j} \times (dp^1_{n - m, n - m, \sum{a_i}} - dp^1_{n - m, l - j - 1, \sum{a_i}} - dp^1_{n - m, n - m, j - 1} + dp^1_{n - m, l - j - 1, j - 1})} \]其中，\(dp^1_{n - m, l - j - 1, \sum{a_i}}\) 在前缀和后变成赢得不超过 \(l - j - 1\) 场a类比赛的概率，由于dp1数组第三维的计算在大概200停止，\(dp^1_{n - m, j, \sum{a_i}}\) 可以用类似于求dp2的方法求出。则有
\[ans = \sum{dp^2_{m, j} \times (1 - dp^1_{n - m, l - j - 1, \sum{a_i}} - dp^1_{n - m, n - m, j - 1} + dp^1_{n - m, l - j - 1, j - 1})} \]需要注意的是，在计算dp数组和答案 \(ans\) 的时候，都要注意判定防止数组下标越界（出现负数下标）；另外，由于此题对精度的要求仅为 \(10^{-6}\)，dp时可以用long long数组存储而不是long double，防止丢精度（亲测，被long double玩了QwQ）。
代码
#include <bits/stdc++.h>
#define LL long long
#define double long double
#define pii pair<int, int>
using namespace std;
int ps[205];
vector<int> p;
vector<pii> a;
vector<LL> pon(205, 0.0), powi(205, 0.0); //使用long long防止丢精度
vector<vector<LL> > dp(205, vector<LL>(405, 0)); //dp数组均被滚动优化掉一维
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
p.push_back(0);
a.push_back({ 0, 0 });
int n, l, k, c;
cin >> n >> l >> k;
for (int i = 1; i <= n; i++)
cin >> ps[i];
for (int i = 1; i <= n; i++)
{
cin >> c;
if (c < 0)
p.push_back(ps[i]);
else
a.push_back({ c, ps[i] });
}
//计算dp1数组
dp[0][k] = 1e12;
for (int i = 1; i < a.size(); i++)
for (int j = i; j >= 0; j--)
for (int m = 400; m >= 0; m--)
dp[j][m] = dp[j][m] * (100 - a[i].second) / 100 + (m >= a[i].first && j ? dp[j - 1][m - a[i].first] * a[i].second / 100 : 0); //三元运算符用于特判防止下标越界，以下同
for (int i = 1; i <= 400; i++) //前缀和
dp[0][i] += dp[0][i - 1];
for (int i = 1; i < a.size(); i++)
{
dp[i][0] += dp[i - 1][0];
for (int j = 1; j <= 400; j++)
dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
}
//同为dp1数组
powi[0] = 1e12;
for (int i = 1; i < a.size(); i++)
for (int j = i; j >= 0; j--)
powi[j] = powi[j] * (100 - a[i].second) / 100 + (j ? powi[j - 1] * a[i].second / 100 : 0);
for (int i = 1; i < a.size(); i++) //前缀和
powi[i] += powi[i - 1];
//计算dp2数组
pon[0] = 1e12;
for (int i = 1; i < p.size(); i++)
for (int j = i; j >= 0; j--)
pon[j] = pon[j] * (100 - p[i]) / 100 + (j ? pon[j - 1] * p[i] / 100 : 0);
//计算答案
double ans = 0.0;
for (int i = max(l - (int)a.size() + 1, 0); i < p.size(); i++)
ans += (double)pon[i] / 1e12 * ((double)((LL)1e12 - (l - i > 0 ? powi[l - i - 1] : 0) - (i ? dp[a.size() - 1][i - 1] : 0) + (l - i > 0 && i ? dp[l - i - 1][i - 1] : 0)) / 1e12);
printf("%.12LF\n", ans);
}
最后祝各位顺利AC。 >w<
标签：比赛,int,题解,sum,long,CF167B,100,dp From： https://www.cnblogs.com/ItsAiHAn/p/18020067