动态DP（支持修改的DP）
BB
网络赛要凉 QAQQQQ
Introduction
DDP是将DP方程化为矩阵连乘形式后，利用矩阵乘法的结合律，将其放到线段树中维护，并可支持修改值并快速取得修改后的DP值的操作
- P4719 【模板】动态 DP 题解
https://www.luogu.org/problemnew/solution/P4719
MAZE - 2019牛客暑期多校训练营（第二场）
Description
给定一个N*M矩阵b，矩阵上为1的点是障碍点，0的点是可通行点，从点b(i,j)可以走向b(i+1,j),b(i,j-1),b(i,j+1)，且不能走回原来走过来的点（指相邻点）。现有两个操作，操作1是将点b(i,j)转换状态，即原来是可通行点则转为障碍点，反之则相反；操作2是询问从点b(1,u)到点b(n,v)的路径方案数。
Sample Input
2 2 3
00
00
2 1 2
1 1 2
2 1 2
Sample Output
2
1
Solution
#include<bits/stdc++.h>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;
const int N = (int)5e4 + 15;
const int MOD = 1000000007;
struct Matrix {
static int n;
int mat[11][11];
inline void init() {
for(int i = 0; i < 11; i++) {
mat[i][0] = 0;
}
}
};
int Matrix::n;
Matrix m0, seg[N << 2];
bool a[N][11];
inline void mulMatrix(const Matrix& a, const Matrix& b, Matrix& ret) {
for(int i = 0; i < Matrix::n; i++) {
for(int j = 0; j < Matrix::n; j++) {
ret.mat[i][j] = 0;
for(int k = 0; k < Matrix::n; k++) {
ret.mat[i][j] = (ret.mat[i][j] + (ll)a.mat[i][k] * b.mat[k][j] % MOD) % MOD;
}
}
}
}
inline void updateMatrix(int pos, int m, int rt) {
for(int i = 0; i < m; i++) {
bool ok = true;
for(int j = i; j >= 0; j--) {
ok &= a[pos][j];
seg[rt].mat[i][j] = ok;
}
ok = true;
for(int j = i; j < m; j++) {
ok &= a[pos][j];
seg[rt].mat[i][j] = ok;
}
}
}
inline void build(int n, int mm, int l, int r, int rt) {
if(l == r) {
int pos = n - l + 1;
updateMatrix(pos, mm, rt);
return;
}
int m = (l + r) >> 1;
build(n, mm, lson);
build(n, mm, rson);
mulMatrix(seg[rt << 1], seg[rt << 1 | 1], seg[rt]);
}
inline void update(int pos, int y, int n, int mm, int l, int r, int rt) {
if(l == r) {
pos = n - pos + 1;
a[pos][y] = !a[pos][y];
updateMatrix(pos, mm, rt);
return;
}
int m = (l + r) >> 1;
if(pos <= m) {
update(pos, y, n, mm, lson);
} else {
update(pos, y, n, mm, rson);
}
mulMatrix(seg[rt << 1], seg[rt << 1 | 1], seg[rt]);
}
int main() {
int n, m, q;
while(~scanf("%d%d%d", &n, &m, &q)) {
Matrix::n = m;
for(int i = 1, tmp; i <= n; i++) {
for(int j = 0; j < m; j++) {
scanf("%1d", &tmp);
a[i][j] = !tmp;
}
}
Matrix res;
if(n > 1) {
build(n, m, 1, n - 1, 1);
}
while(q--) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if(op == 1) {
if(x == 1) {
a[x][y - 1] = !a[x][y - 1];
} else {
update(n - x + 1, y - 1, n, m, 1, n - 1, 1);
}
} else {
m0.init();
x--;
y--;
for(int i = x; i >= 0; i--) {
if(!a[1][i]) {
break;
}
m0.mat[i][0] = 1;
}
for(int i = x; i < m; i++) {
if(!a[1][i]) {
break;
}
m0.mat[i][0] = 1;
}
if(n > 1) {
mulMatrix(seg[1], m0, res);
printf("%d\n", res.mat[y][0]);
} else {
printf("%d\n", m0.mat[y][0]);
}
}
}
}
}
【模板】动态 DP - Luogu P4719
Description
给定一棵n个点的树，点带点权。
有m次操作，每次操作给定x,y，表示修改点x的权值为y。
你需要在每次操作之后求出这棵树的最大权独立集的权值大小。
Sample Input
10 10
-11 80 -99 -76 56 38 92 -51 -34 47
2 1
3 1
4 3
5 2
6 2
7 1
8 2
9 4
10 7
9 -44
2 -17
2 98
7 -58
8 48
3 99
8 -61
9 76
9 14
10 93
Sample Output
186
186
190
145
189
288
244
320
258
304
Solution
懒得写题解，屯个板
题解自行翻上述链接
#include<bits/stdc++.h>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
const int N = (int)1e5 + 15;
const int inf = 0x3f3f3f3f;
struct Matrix {
int mat[2][2];
inline Matrix operator * (const Matrix& b) const {
Matrix ret;
for(int i = 0; i < 2; i++) {
for(int j = 0; j < 2; j++) {
ret.mat[i][j] = 0;
for(int k = 0; k < 2; k++) {
ret.mat[i][j] = max(ret.mat[i][j], mat[i][k] + b.mat[k][j]);
}
}
}
return ret;
}
};
struct edge {
int v, nxt;
};
int val[N];
int son[N], sz[N], dpt[N], fa[N];
int mptot, mp[N << 2], top[N << 2], belong[N << 2], ed[N];
Matrix seg[N << 2], upVal[N];
int head[N], tot;
edge e[N << 1];
int dp[N][2], ldp[N][2];
inline void init() {
memset(head, -1, sizeof(head));
tot = 0;
}
inline void addEdge(int u, int v) {
e[tot] = edge{v, head[u]};
head[u] = tot++;
}
inline void dfs(int u){
sz[u] = 1;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(v == fa[u]) continue;
fa[v] = u;
dpt[v] = dpt[u] + 1;
dfs(v);
sz[u] += sz[v];
if(son[u] == 0 || sz[son[u]] < sz[v]) {
son[u] = v;
}
}
}
inline void buildTree(int u, int rt, int n){
mp[u] = ++mptot;
belong[mptot] = u;
top[u] = rt;
ed[rt] = mptot;
ldp[u][1] = val[u];
if(son[u]) {
buildTree(son[u], rt, n);
dp[u][0] += max(dp[son[u]][0], dp[son[u]][1]);
dp[u][1] += dp[son[u]][0];
}
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(v == fa[u] || v == son[u]) continue;
buildTree(v, v, n);
ldp[u][0] += max(dp[v][0], dp[v][1]);
ldp[u][1] += dp[v][0];
}
dp[u][0] += ldp[u][0];
dp[u][1] += ldp[u][1];
}
inline void build(int l, int r, int rt) {
if(l == r) {
int u = belong[l];
upVal[u].mat[0][0] = upVal[u].mat[0][1] = ldp[u][0];
upVal[u].mat[1][0] = ldp[u][1];
upVal[u].mat[1][1] = -inf;
seg[rt] = upVal[u];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
seg[rt] = seg[rt << 1] * seg[rt << 1 | 1];
}
inline void update(int pos, int l, int r, int rt) {
if(l == r) {
seg[rt] = upVal[belong[l]];
return;
}
int m = (l + r) >> 1;
if(pos <= m) {
update(pos, lson);
} else {
update(pos, rson);
}
seg[rt] = seg[rt << 1] * seg[rt << 1 | 1];
}
inline Matrix query(int ql, int qr, int l, int r, int rt) {
if(ql <= l && r <= qr) {
return seg[rt];
}
int m = (l + r) >> 1;
if(m < ql) {
return query(ql, qr, rson);
} else if(qr <= m) {
return query(ql, qr, lson);
} else {
return query(ql, qr, lson) * query(ql, qr, rson);
}
}
inline void change(int u, int x) {
upVal[u].mat[1][0] += x - val[u];
val[u] = x;
while(u) {
int now = top[u];
Matrix pre = query(mp[now], ed[now], 1, mptot, 1);
update(mp[u], 1, mptot, 1);
Matrix cur = query(mp[now], ed[now], 1, mptot, 1);
u = fa[now];
upVal[u].mat[0][0] += (max(cur.mat[0][0], cur.mat[1][0]) - max(pre.mat[0][0], pre.mat[1][0]));
upVal[u].mat[1][0] += (cur.mat[0][0] - pre.mat[0][0]);
upVal[u].mat[0][1] = upVal[u].mat[0][0];
}
}
int main() {
int n, m;
while(~scanf("%d%d", &n, &m)) {
init();
for(int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
for(int i = 1; i <= n - 1; i++) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
dfs(1);
buildTree(1, 1, n);
build(1, mptot, 1);
while(m--) {
int u, x;
scanf("%d%d", &u, &x);
change(u, x);
Matrix mat = query(mp[1], ed[1], 1, mptot, 1);
printf("%d\n", max(mat.mat[0][0], mat.mat[1][0]));
}
}
}
