云建站自动建站系统源码,网站升级及政务新媒体建设方案,网站开发维护前景,广东省建设厅的注册中心网站首页动态DP——广义矩阵加速SP1716 GSS3 - Can you answer these queries IIIdescriptionsolutioncode[NOIP2018 提高组] 保卫王国descriptionsolutioncode动态DP能矩阵加速要满足外层操作符对内层操作符具有分配率加法对于乘法就具有分配率(ab)*ca*cb*c
SP1716 GSS3 - Can you a…
动态DP——广义矩阵加速SP1716 GSS3 - Can you answer these queries IIIdescriptionsolutioncode[NOIP2018 提高组] 保卫王国descriptionsolutioncode动态DP能矩阵加速要满足外层操作符对内层操作符具有分配率加法对于乘法就具有分配率(ab)*ca*cb*c
SP1716 GSS3 - Can you answer these queries III
description
solution
设fi:f_i:fi: 前iii个数的最大子段和gi:g_i:gi: 以iii结尾的最大子段和
gimax(gi−1ai,ai)g_i\max(g_{i-1}a_i,a_i)gimax(gi−1ai,ai)
fimax(fi−1,gi)f_imax(f_{i-1},g_i)fimax(fi−1,gi)
max\maxmax对于具有分配率max(ac,bc)cmax(a,b)
所以广义的矩阵加速就是在原始的矩阵上∗→*\rightarrow ∗→→max\rightarrow \max→max
为了套用矩阵乘法改写一下gimax(gi−1ai,ai,−inf),fimax(fi−1,gi,−inf)g_i\max(g_{i-1}a_i,a_i,-inf),f_i\max(f_{i-1},g_i,-inf)gimax(gi−1ai,ai,−inf),fimax(fi−1,gi,−inf) [fi−1gi−10]×[0aiai−infaiai−inf−inf0][figi0]\begin{bmatrix} f_{i-1}\\ g_{i-1}\\ 0\\ \end{bmatrix} \times \begin{bmatrix} 0a_ia_i\\ -infa_ia_i\\ -inf-inf0\\ \end{bmatrix} \begin{bmatrix} f_i\\ g_i\\ 0 \end{bmatrix} ⎣⎡fi−1gi−10⎦⎤×⎣⎡0−inf−infaiai−infaiai0⎦⎤⎣⎡figi0⎦⎤
code
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 50005
#define inf 0x3f3f3f3f
struct matrix {int c[3][3];matrix operator * ( const matrix t ) const {matrix ans;for( int i 0;i 3;i )for( int j 0;j 3;j )ans.c[i][j] -inf;for( int i 0;i 3;i )for( int j 0;j 3;j )for( int k 0;k 3;k )ans.c[i][j] max( ans.c[i][j], c[i][k] t.c[k][j] );return ans;}
}t[maxn 2], ret;
int n, Q;
int a[maxn];void New( int num, int pos ) {t[num].c[0][0] t[num].c[0][1] t[num].c[2][0] t[num].c[2][1] a[pos];t[num].c[0][2] t[num].c[1][0] t[num].c[1][2] -inf;t[num].c[1][1] t[num].c[2][2] 0;
}void build( int num, int l, int r ) {if( l r ) {New( num, l );return;}int mid ( l r ) 1;build( num 1, l, mid );build( num 1 | 1, mid 1, r );t[num] t[num 1] * t[num 1 | 1];
}void modify( int num, int l, int r, int pos ) {if( l r ) {New( num, pos );return;}int mid ( l r ) 1;if( pos mid ) modify( num 1, l, mid, pos );else modify( num 1 | 1, mid 1, r, pos );t[num] t[num 1] * t[num 1 | 1];
}matrix query( int num, int l, int r, int L, int R ) {if( L l r R ) return t[num];int mid ( l r ) 1;if( R mid ) return query( num 1, l, mid, L, R );else if( mid L ) return query( num 1 | 1, mid 1, r, L, R );else return query( num 1, l, mid, L, R ) * query( num 1 | 1, mid 1, r, L, R );
}int main() {scanf( %d, n );for( int i 1;i n;i )scanf( %d, a[i] );build( 1, 1, n );scanf( %d, Q );while( Q -- ) {int opt, l, r;scanf( %d %d %d, opt, l, r );if( ! opt ) a[l] r, modify( 1, 1, n, l );else {ret query( 1, 1, n, l, r );printf( %d\n, ret.c[2][1] );}} return 0;
}[NOIP2018 提高组] 保卫王国
description
solution
考虑对于一条链的简单转移设dpi,0/1:idp_{i,0/1}:idpi,0/1:i点不选/选的最小花费
矩阵形式 [fi−1,0fi−1,1]×[−inf0aiai][fi,0fi,1]\begin{bmatrix} f_{i-1,0}\\ f_{i-1,1}\\ \end{bmatrix} \times \begin{bmatrix} -inf0\\ a_ia_i\\ \end{bmatrix} \begin{bmatrix} f_{i,0}\\ f_{i,1}\\ \end{bmatrix} [fi−1,0fi−1,1]×[−infai0ai][fi,0fi,1] 在树上就是普通的树形DPDPDP设dpi,0/1:idp_{i,0/1}:idpi,0/1:i子树内iii点不选/选的最小花费
dpi,0∑j∈sonidpj,1dp_{i,0}\sum_{j\in son_i}dp_{j,1}dpi,0∑j∈sonidpj,1
dpi,1∑j∈sonimin(dpj,0,dpj,1)dp_{i,1}\sum_{j\in son_i}\min(dp_{j,0},dp_{j,1})dpi,1∑j∈sonimin(dpj,0,dpj,1)
对于某个点转移是固定的且min\minmin对同样具有分配率
考虑动态DPDPDP树链剖分轻重链断树将矩阵放到线段树上合并加速
gi,0∑j∈soni,j≠MaxSonifj,1g_{i,0}\sum_{j\in son_i,j≠MaxSon_i}f_{j,1}gi,0∑j∈soni,jMaxSonifj,1
gi,1∑j∈soni,j≠MaxSonimin(fj,0,fj,1)g_{i,1}\sum_{j\in son_i,j≠MaxSon_i}\min(f_{j,0},f_{j,1})gi,1∑j∈soni,jMaxSonimin(fj,0,fj,1)
矩阵形式 [fMaxSoni,0fMaxSoni,1]×[−infgi,0gi,1gi,1][fi,0fi,1]\begin{bmatrix} f_{MaxSon_i,0}\\ f_{MaxSon_i,1}\\ \end{bmatrix} \times \begin{bmatrix} -infg_{i,0}\\ g_{i,1}g_{i,1}\\ \end{bmatrix} \begin{bmatrix} f_{i,0}\\ f_{i,1}\\ \end{bmatrix} [fMaxSoni,0fMaxSoni,1]×[−infgi,1gi,0gi,1][fi,0fi,1] 一条重链顶点的DPDPDP值就是这条链上所有矩阵“乘积”
具体细节详情请见完美代码非常好懂只是长了点而已
code
#include cstdio
#include vector
#include cstring
#include iostream
using namespace std;
#define inf 1e18
#define int long long
#define maxn 100005
vector int G[maxn];
char type[4];
int n, m, cnt;
int p[maxn], siz[maxn], fa[maxn], son[maxn], dfn[maxn], id[maxn], top[maxn], rnk[maxn], Left[maxn], Right[maxn], dep[maxn];
int f[maxn][2], g[maxn][2], ans[2][2], MS[2][2];
int matrix[maxn 2][2][2];void dfs1( int u, int father ) {siz[u] 1, fa[u] father, dep[u] dep[father] 1, f[u][1] p[u];for( auto v : G[u] ) {if( v father ) continue;else dfs1( v, u );siz[u] siz[v];f[u][0] f[v][1];f[u][1] min( f[v][0], f[v][1] );if( ! son[u] || siz[v] siz[son[u]] )son[u] v;}
}
/*
f[x][0/1]:x不选/选
f[x][0]f[son][1]
f[x][1]min(f[son][0],f[son][1])
g[x][0]:定义等同于f[x][0]但只含轻儿子
g[x][1]:定义等同于f[x][1]但只含轻儿子
left[x]-right[x]:一条重链所管辖的区间(dfn序)
*/
void dfs2( int u, int t ) {dfn[u] Left[u] Right[u] cnt, id[cnt] u, top[u] t;g[u][1] p[u];if( ! son[u] ) return;else dfs2( son[u], t );Right[u] Right[son[u]];for( auto v : G[u] ) {if( v fa[u] || v son[u] ) continue;else dfs2( v, v );g[u][0] f[v][1];g[u][1] min( f[v][0], f[v][1] );}
}
/*
动态dp
* - - min
*/
void pushup( int num ) {for( int i 0;i 2;i )for( int j 0;j 2;j )matrix[num][i][j] inf;for( int i 0;i 2;i )for( int j 0;j 2;j )for( int k 0;k 2;k )matrix[num][i][j] min( matrix[num][i][j], matrix[num 1][i][k] matrix[num 1 | 1][k][j] );
}
/*
|inf A[u]|
|B[u] B[u]|
*
|f[maxson][0]|
|f[maxson][1]|f[u][0]
f[u][1]
*/
void build( int num, int l, int r ) {if( l r ) {rnk[id[l]] num;matrix[num][0][0] inf;matrix[num][0][1] g[id[l]][0];matrix[num][1][0] matrix[num][1][1] g[id[l]][1];return;}int mid ( l r ) 1;build( num 1, l, mid );build( num 1 | 1, mid 1, r );pushup( num );
}void modify( int num, int l, int r, int pos ) {if( l r ) return;int mid ( l r ) 1;if( pos mid ) modify( num 1, l, mid, pos );else modify( num 1 | 1, mid 1, r, pos );pushup( num );
}void query( int num, int l, int r, int L, int R ) {if( L l r R ) {for( int i 0;i 2;i )for( int j 0;j 2;j )MS[i][j] inf;for( int i 0;i 2;i )for( int j 0;j 2;j )for( int k 0;k 2;k )MS[i][j] min( MS[i][j], ans[i][k] matrix[num][k][j] );memcpy( ans, MS, sizeof( MS ) );return;}int mid ( l r ) 1;if( L mid ) query( num 1, l, mid, L, R );if( mid R ) query( num 1 | 1, mid 1, r, L, R );
}void modify( int x, int t ) {if( t -1 ) {matrix[rnk[x]][0][0] inf;matrix[rnk[x]][0][1] g[x][0];matrix[rnk[x]][1][0] matrix[rnk[x]][1][1] g[x][1];}else if( t 0 ) {//不能驻扎军队f[x][1]贡献必须无 设其转移矩阵inf 最后取min才会不选matrix[rnk[x]][0][0] matrix[rnk[x]][1][0] matrix[rnk[x]][1][1] inf;matrix[rnk[x]][0][1] g[x][0];}else {//必须驻扎军队f[x][1]贡献必须有 设f[x][0]转移矩阵inf 取min一定选f[x][1]matrix[rnk[x]][0][0] matrix[rnk[x]][0][1] inf;matrix[rnk[x]][1][0] matrix[rnk[x]][1][1] g[x][1];}modify( 1, 1, n, dfn[x] );//线段树的矩阵更新 while( x ) {//爬链x top[x];ans[0][0] ans[1][1] 0;ans[0][1] ans[1][0] inf;//广义矩阵下的单位矩阵定义query( 1, 1, n, Left[x], Right[x] );//查询整条重链´ int IS f[x][0], SI f[x][1];f[x][0] min( ans[0][0], ans[0][1] );f[x][1] min( ans[1][0], ans[1][1] );if( x 1 ) return;int y fa[x];//轻链跳到重链上g[y][0] ( f[x][1] - SI );//更新y(不选)的轻儿子贡献 减去原来的加上现在的f[x][1]g[y][1] ( min( f[x][0], f[x][1] ) - min( SI, IS ) );//更新y(选)的轻儿子贡献减去原来的min加上现在的min(f[x][1],f[x][0])matrix[rnk[y]][0][1] g[y][0];matrix[rnk[y]][1][0] matrix[rnk[y]][1][1] g[y][1];modify( 1, 1, n, dfn[y] );x y;}
}signed main() {freopen( defense.in, r, stdin );freopen( defense.out, w, stdout );scanf( %lld %lld %s, n, m, type );for( int i 1;i n;i )scanf( %lld, p[i] ); for( int i 1, u, v;i n;i ) {scanf( %lld %lld, u, v );G[u].push_back( v );G[v].push_back( u );}dfs1( 1, 0 );dfs2( 1, 1 );build( 1, 1, n );while( m -- ) {int a, x, b, y;scanf( %lld %lld %lld %lld, a, x, b, y );if( dep[a] dep[b] ) swap( a, b ), swap( x, y );
//先修改上面的点的话 后面在下面的点的修改其实会影响上面的点 那么之前上面的点的转移就是虚假的modify( a, x ), modify( b, y );if( min( f[1][0], f[1][1] ) inf ) printf( -1\n );else printf( %lld\n, min( f[1][0], f[1][1] ) );modify( a, -1 ), modify( b, -1 );//询问独立最后要重置矩阵}return 0;
}
