Matrix operator * (const Matrix &B)const
{
Matrix res;
for(int i = 0; i < 4; ++ i)
{
for(int j = 0; j < 4; ++ j)
{
for(int k = 0; k < 4; ++ k)res.a[i][j] = max(res.a[i][j], a[i][k] + B.a[k][j]);
}
}
return res;
}
接下来，就是构造矩阵，使得我们之前的式子成立了：
$
\begin{bmatrix}
f{n, 0} & f{n, 1} & f{n, 2} & f{n, 3}
\end{bmatrix} =
\begin{bmatrix}
f{n – 1, 0} & f{n – 1, 1} & f{n – 1, 2} & f{n – 1, 3}
\end{bmatrix}
\times
\begin{bmatrix}
0 & w_i & -\infty & -\infty \
0 & -\infty & w_i & -\infty \
0 & -\infty & -\infty & w_i \
0 & -\infty & -\infty & -\infty
\end{bmatrix}
$
然后，因为要进行修改，所以考虑把这个矩阵放到线段树上维护。
如果将广义矩阵乘法打包，线段树其实就是普通的单点修改 + 区间查询（甚至不一定需要查询）
然后，就到了求结果的时候，不知道为什么有的TJ维护四棵线段树，事实上一棵就够
考虑刚刚做了四次DP的做法，其实只需要把相应的矩阵用线段树区间查询乘起来就能得到结果，这样写在LUOGU可以通过。
但是如果你的OJ不支持你带这样大的常数，可能需要学习第一篇TJ中的矩阵对角线性质，总之结论是对角线取最大值。
#include
using namespace std;
typedef long long LL;
const int N = 40005;
const LL INF = 1e15;
int n, m, w[N];
struct Matrix
{
LL a[4][4];
Matrix()
{
for (int i = 0; i < 4; ++ i)
{
for (int j = 0; j < 4; ++ j)a[i][j] = -INF;
}
}
Matrix operator * (const Matrix &B)const
{
Matrix res;
for(int i = 0; i < 4; ++ i)
{
for(int j = 0; j < 4; ++ j)
{
for(int k = 0; k < 4; ++ k)res.a[i][j] = max(res.a[i][j], a[i][k] + B.a[k][j]);
}
}
return res;
}
};
Matrix tr[N << 2];
void pushup(int u){tr[u] = tr[u << 1] * tr[u 1;
build(u << 1, l, mid);
build(u 1;
if (pos <= mid)modify(u << 1, l, mid, pos, v);
else modify(u << 1 | 1, mid + 1, r, pos, v);
pushup(u);
}
Matrix query(int u, int l, int r, int L, int R)
{
if (L 1;
Matrix res;
if (L <= mid && mid < R)return query(u << 1, l, mid, L, R) * query(u << 1 | 1, mid + 1, r, L, R);
else if (L <= mid)return query(u << 1, l, mid, L, R);
else if (mid < R)return query(u << 1 | 1, mid + 1, r, L, R);
else return res;
}
void get()
{
// f[(i, 0), (i, 1), (i, 2), (i, 3)] = f[(i - 1, 0), (i - 1, 1), (i - 1, 2), (i - 1, 3)] * X
/*
X = [0, ai, -INF, -INF]
[0, -INF, ai, -INF]
[0, -INF, -INF, ai]
[0, -INF, -INF, -INF]
*/
LL res = -INF;
for (int i = 0; i < 4; i ++)res = max(res, tr[1].a[i][i]);
printf("%lld\n", res);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++)scanf("%d", &w[i]);
build(1, 1, n);
get();
scanf("%d", &m);
while (m --)
{
int x, y;
scanf("%d%d", &x, &y);
modify(1, 1, n, x, y);
get();
}
return 0;
}
[T2]
思考到半路脑子烧了以为第一遍DFS根上得到结果也不对然后就放弃了。
实际上就是一个换根DP，换言之两次DFS解决的东西。
每个点带电的情况只有以下三种：
- 自己有电
- 子树中的一个儿子有电（不管怎么来的）通过边给电
- 父亲有电（不管怎么来的）通过边给电
暂时性失明第三条，前两条是好处理的。
令 f_u 为当前节点带电的概率，p_u表示 u 本身有电的概率， E(u, v) 表示 (u, v) 间能够导通的概率。
对于第一条， f_u = p_u。
处理第二条，运用 P(A \cup B) = P(A) + P(B) – P(A)\cdot P(B)，这里的 P(A) = f_u, P(B) = f_v \cdot E(u,v)。
接下来考虑第三条，也就是所谓的 “换根”。
事实上我们根节点求出来的结果已经是对的（因为根节点没有父亲向它导电了），考虑如何向儿子转移。
设根是 u， 子节点是 v
因为 v 不能在没电的情况下给 u 电，所以我们现在要排除 v 这一链路上所提供的概率。
即现在未知 P(A)，已知 P(B) = f_v \cdot E(u, v)，P(A \cup B) = f_u = P(A) + P(B) – P(A)\cdot P(B)，解方程得到 P(A) = \frac{f_u – P(B)}{1 – P(B)}。
接下来就和第二条很像了，已知 P'(A) = P(A) * E(u, v), P'(B) = f_v， P(A \cup B) = P(A) + P(B) – P(A)\cdot P(B) 就可以了。
请注意，由于 P(A) = \frac{f_u – P(B)}{1 – P(B)}，而有可能出现除 0 错误，因此如果 P(B) = 1 ，就是 v 怎么样都有电的话，自然不需要父亲的馈赠，直接往下 DFS 就行。
#include
using namespace std;
const int N = 500005;
const double eps = 1e-8;
int n;
int h[N], e[N << 1], w[N << 1], ne[N << 1], idx;
void add(int a, int b, int c){e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;}
double f[N];
void dfs1(int u, int father)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == father)continue;
dfs1(j, u);
double pa = f[u], pb = f[j] * (w[i] / 100.0);
//P(A) = f[u], P(B) = f[j] * w[i] / 100.0
f[u] = pa + pb - pa * pb;
}
}
void dfs2(int u, int father)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == father)continue;
//P(A) = ? , P(B) = f[j] * (w[i] / 100.0)
//P(A) + P(B) - P(A) * P(B) = P(C)
//P(A)*(1 - P(B)) = P(C) - P(B)
//P(A) = (P(C) - P(B)) / (1 - P(B))
double pb = f[j] * (w[i] / 100.0), pc = f[u];
if (fabs(pb - 1.00) < eps)
{
dfs2(j, u);
continue;
}
double pa = (pc - pb) / (1.0 - pb);
double pap = pa * (w[i] / 100.0), pbp = f[j];
//P'(A) = P(A), P'(B) = f[j]
//P'(A) + P'(B) - P'(A) * P'(B)
f[j] = pap + pbp - pap * pbp;
dfs2(j, u);
}
}
int main()
{
freopen("charger.in", "r", stdin);
freopen("charger.out", "w", stdout);
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 1; i < n; i ++)
{
int a, b, p;
scanf("%d%d%d", &a, &b, &p);
add(a, b, p);
add(b, a, p);
}
for (int i = 1, x; i <= n; i ++)
{
scanf("%d", &x);
f[i] = x / 100.0;
}
dfs1(1, -1);
dfs2(1, -1);
double res = 0;
for (int i = 1; i <= n; i ++)res += f[i];
printf("%.6lf", res);
return 0;
}
[T3]
什么大型卡常现场，这个卡常比去年矩阵乘法每八次再取模的卡常还狠。
到底是谁在创造这些奇奇怪怪的优化方法的
总之就是一个轮廓线DP，但是不想动了，大概就是枚举轮廓线上状态去做，属于插头DP的一种。
所以到底谁家好人提高组会放插头DP。
T4/T5/T6不是我能力范围内的样子，再看看.