[LibreOJ 6433][PKUSC2018]最大前缀和
给你一个长为\(n\)的整数序列\(a\)，求出将序列随机打乱之后的最大前缀和（不能选空前缀！）的期望，答案乘上\(n!\)之后对\(998244353\)输出。
\(1\leq n\leq 20, \sum_{i = 1}^n |a_i|\leq 10^9\)。
[UOJ 333][NOIP2017]宝藏
啊啊啊爽到力，，，
过去太池沼力，没有做出来惹。现在看了看可能比较简单罢……
定义状态\(d_{i, S}\)表示当前已经被覆盖的点集为\(S\)，然后当前的生成树已经考虑到了第\(i\)层，转移看起来很毒……
所以预处理一个点集到另一个点集只走一步边来扩展，最优解是多少，然后转移就方便力……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
const int maxn = 12;
int G[15][15];
const int INF = 0x3f3f3f3f;
void add_edge(int u, int v, int d) {
G[u][v] = std::min(G[u][v], d);
G[v][u] = std::min(G[v][u], d);
}
int n;
int g1[(1 << maxn)][15], g2[(1 << maxn)][(1 << maxn)];
void process() {
for(int s = 1; s < (1 << n); s ++) {
for(int i = 1; i <= n; i ++) {
g1[s][i] = INF;
for(int j = 0; j < n; j ++) {
if((1 << j) & s) {
g1[s][i] = std::min(g1[s][i], G[j + 1][i]);
}
}
}
}
for(int s = 1; s < (1 << n); s ++) {
int k = (1 << n) - 1; k = k & (~s);
for(int t = k; t > 0; t = (t - 1) & k) {
g2[s][t] = 0;
for(int i = 1; i <= n; i ++) {
if((1 << (i - 1)) & t) {
if(g1[s][i] == INF) {
g2[s][t] = INF; break;
}
g2[s][t] += g1[s][i];
}
}
}
}
}
using ll = long long;
ll d[14][(1 << maxn)];
ll dp() {
for(int s = 0; s < (1 << n); s ++) {
d[1][s] = INF;
}
for(int i = 0; i < n; i ++) {
d[1][(1 << i)] = 0;
}
for(int i = 2; i <= n; i ++) {
for(int s = 1; s < (1 << n); s ++) {
d[i][s] = INF;
for(int t = (s - 1) & s; t != 0; t = (t - 1) & s) {
d[i][s] = std::min(d[i][s], d[i - 1][t] + (ll(i - 1)) * g2[t][s ^ t]);
}
}
}
ll ans = INF;
for(int i = 1; i <= n; i ++) {
ans = std::min(ans, d[i][(1 << n) - 1]);
}
return ans;
}
int main() {
memset(G, 0x3f, sizeof(G));
int m; scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
add_edge(u, v, w);
}
process(); printf("%lld\n", dp());
return 0;
}
[BZOJ 3925][ZJOI2015]地震后的幻想乡
赛艇，赛艇.jpg
首先这个问题的本质就是让你求一个边权在\([0, 1]\)间均匀随机分布的无向图的MST的最大边边权的期望……
有一个很经典的式子：
\[E = \int_0^1 p(\geq x)\,\mathrm{d}x\]
然后考虑那个\(p\)咋整。
首先对于每个包含1的点集（我们不妨假设是从点1开始扩展）\(S\)，式子可以这么写（这里不妨用\(T\)来表示两个点集间的边的数目）：
\[p_{S, x} = \sum_{1\in S_0 \subset S} (1 - x)^{T(S_0, S - S_0)}(1 - p_{S_0, x})\]
显然答案是\(\int_0^1 p_{S, x}\,\mathrm{d}x\)，但这玩咋求……
然后我们定义一个状态\(d\)：
\[d_{S, k} = \int_0^1 (1 - x)^k p_{S, x}\,\mathrm{d}x\]
把其中的\(p\)展开，整理一下，得到：
\[
\begin{aligned}
d_{S, k}=&\sum_{1\in S_0 \subset S}(\int_0^1(1 - x)^{T(S, S - S_0) + k}\,\mathrm{d}x\\
& - \int_0^1(1 - x)^{T(S, S - S_0) + k}\,p_{S_0,\,x}\,\mathrm{d}x)
\end{aligned}
\]
\begin{aligned}
d_{S, k}=&\sum_{1\in S_0 \subset S}(\int_0^1(1 - x)^{T(S, S - S_0) + k}\,\mathrm{d}x\\
& - \int_0^1(1 - x)^{T(S, S - S_0) + k}\,p_{S_0,\,x}\,\mathrm{d}x)
\end{aligned}
\]
里面有两大块定积分，前一块还看起来蛮好求的，但后面一块……
不就是\(d_{S_0, T(S, S - S_0) + k}\) 吗？
然后这样整个$d$就可以搞一波状压DP了。
然后观察\(d_{S, 0}\)（这里不妨假设S为全集）：
\[d_{S, 0}=\int_0^1(1 - x)^0 p_{S, x}\,\mathrm{d}x = \int_0^1 p_{S, x}\,\mathrm{d}x\]
这不就是我们要的答案吗？
至于边界处理，\(d_{\{1\}, x}\)全部搞成0就行。
代码：
/**************************************************************
Problem: 3925
User: danihao123
Language: C++
Result: Accepted
Time:100 ms
Memory:1272 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <bitset>
typedef double R;
const int maxn = 11;
const int maxm = 50;
int edge[maxm][2];
int n, m;
R d[1 << 10][maxm];
bool vis[1 << 10][maxm];
R f(int s, int k) {
if(s == 1) return 0;
if(vis[s][k]) return d[s][k];
d[s][k] = 0;
int lit_s = s >> 1;
for(int lit_s0 = (lit_s - 1) & lit_s; ; lit_s0 = (lit_s0 - 1) & lit_s) {
int s0 = lit_s0 * 2 + 1;
int t = 0;
for(int i = 1; i <= m; i ++) {
int u = edge[i][0], v = edge[i][1];
if(((1 << u) & s) == 0 || ((1 << v) & s) == 0) continue;
if((((1 << u) & s0) == 0) ^ (((1 << v) & s0) == 0)) {
t ++;
}
}
int z = k + t;
d[s][k] += 1.00 / ((double(z)) + 1.00) - f(s0, z);
if(s0 == 1) break;
}
vis[s][k] = true;
return d[s][k];
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
int u, v; scanf("%d%d", &u, &v); u --, v --;
edge[i][0] = u, edge[i][1] = v;
}
printf("%.6lf\n", f((1 << n) - 1, 0));
return 0;
}
