sosDP & DDP 學(xué)習(xí)筆記

路人甲Java 2022-12-24 發(fā)布于北京

展開全文

~~純粹是為了節(jié)省篇目所以把這倆合在一起了~~

高維前綴和(sosDP)

~~不是很懂我為什么要在FWT之后學(xué)這個(gè)東西~~

子集和DP Sum over Subsets dynamic programming 一般用來解決這種東西：

\[\forall 0\leq i\leq 2^n-1,\sum_{j\subset i}a[j] \]

直接枚舉子集是 \(\mathcal{O}(3^n)\) 的，用這個(gè)東西做到 \(\mathcal{O}(n\cdot 2^n)\) .

思路&實(shí)現(xiàn)

先考慮維度較低的前綴和。眾所周知，二維前綴和就是四個(gè)矩形容斥一下。但是還有一種寫法是對每一個(gè)維度分別求前綴和：

for ( int i=1; i<=n; i++ )
	for ( int j=1; j<=n; j++ )
		a[i][j]+=a[i-1][j];
for ( int i=1; i<=n; i++ )
	for ( int j=1; j<=n; j++ )
		a[i][j]+=a[i][j-1];

如果維度上升到三維甚至更多，容斥會變得極其不可做，但是這種逐維求和的方式還是可行的。

高維前綴和利用的其實(shí)就是這種按位的思想，加上一個(gè)DP。

以上面的子集問題為例，設(shè) \(dp[i][S]\) 表示狀態(tài)為 \(S\) ，二進(jìn)制最后 \(i\) 位和 \(S\) 不同的子集的信息之和。

對于這種子集關(guān)系，放一張剽來的圖：

容易發(fā)現(xiàn)，我們每次只需要統(tǒng)計(jì)枚舉的當(dāng)前位為 \(0/1\) 的、上一層的子集答案，并且在當(dāng)前位為 \(0\) 的時(shí)候只需要統(tǒng)計(jì)為 \(0\) 的情況。寫成代碼就是（這里把第一維滾掉了w）

for ( int i=0; i<(1<<n); i++ ) f[i]=a[i];
for ( int i=0; i<n; i++ )
	for ( int S=0; S<(1<<n); S++ )
		if ( S&(1<<i) ) f[S]+=f[S^(1<<i)];

超集：如果 \(S_2\subseteq S_1\) ，那么 \(S_1\) 是 \(S_2\) 的超集。

sosDP 同樣可以用來解決超集求和問題，方法是幾乎相同的，可以理解為把子集問題中所有的 \(01\) 反轉(zhuǎn)。

for ( int i=0; i<(1<<n); i++ ) f[i]=a[i];
for ( int i=0; i<n; i++ )
	for ( int S=0; S<(1<<n); S++ )
		if ( !(S&(1<<i)) ) f[S]+=f[S^(1<<i)];

注：更一般的情況下，高維前綴和中這個(gè) += 是將兩個(gè)答案合并，即 f[S]=Merge(f[S],f[S^(1<<i)]) .

習(xí)題

Or Plus Max

給定一個(gè)長度為 \(2^n\) 的序列 \(a\) ，對于 \(1\leq k\leq 2^n-1\) ，求 \(\max\{a[i]+a[j]\},\forall i|j\leq k\) ，\(k\) 取遍 \(1\sim 2^n-1\) 。

\(\forall i|j\leq k\) 這個(gè)條件可以轉(zhuǎn)化為：求出 \(i|j=k\) 的答案，然后前綴 \(\max\) 。而對于 \(i|j=k\) ，又可以轉(zhuǎn)化為 \(i|j\subseteq k\) ，因?yàn)槿绻虺鰜硎莻€(gè)真子集只會讓答案更小。到了這一步，其實(shí)就是求 \(k\) 所有子集中 \(a[i]\) 的最大值和次大值，然后合并答案即可。

//Author: RingweEH
void bmax( int &a,int b ) { a=(a>b) ? a : b; }
const int N=19,INF=0x3f3f3f3f;
struct Node 
{ 
	int mx1,mx2; 
	Node ( int _mx1=-INF,int _mx2=-INF ) : mx1(_mx1),mx2(_mx2) {}
}f[1<<N];
int a[1<<N],n;

Node Merge( Node t1,Node t2 )
{
	Node res=t1;
	if ( t2.mx1>res.mx1 ) res.mx2=res.mx1,res.mx1=t2.mx1,bmax(res.mx2,t2.mx2);
	else bmax( res.mx2,t2.mx1 );
	return res;
}

int main()
{
	n=read(); int m=1<<n;
	for ( int i=0; i<m; i++ ) a[i]=read();

	for ( int i=0; i<m; i++ ) f[i]=Node(a[i]);
	for ( int i=0; i<n; i++ )
		for ( int S=0; S<m; S++ )
			if ( S&(1<<i) ) f[S]=Merge(f[S],f[S^(1<<i)]);

	int ans=0;
	for ( int i=1; i<m; i++ )
		bmax( ans,f[i].mx1+f[i].mx2 ),printf("%d\n",ans );

	return 0;
}

Bits And Pieces

給定一個(gè)長度為 \(n\) 的序列 \(a\) ，求對于所有滿足 \(i<j<k\) 的三元組 \((i,j,k)\) ，\(\max\{a_i|(a_j\&a_k)\}\) .

某一個(gè)數(shù) \(x\) 出現(xiàn)兩次及以上就能被 \(\&\) 出來了，所以可以枚舉 \(a[i]\) 然后統(tǒng)計(jì)對應(yīng)的 \(a[j]\&a[k]\) ，再把 \(a[i]\) 統(tǒng)計(jì)進(jìn)去，順帶滿足大小關(guān)系。

//Author: RingweEH
void Add( int x,int p )
{
	if ( cnt[x]>=2 ) return;
	if ( p==-1 ) { cnt[x]++; return; }
	Add( x,p-1 );
	if ( x&(1<<p) ) Add( x^(1<<p),p-1 );
}

int Get( int x )
{
	int res=0;
	for ( int i=20; i>=0; i-- )
		if ( !(x&(1<<i)) && cnt[res|(1<<i)]>=2 ) res|=(1<<i);
	return res|x; 
}

int main()
{
	n=read();
	for ( int i=1; i<=n; i++ ) a[i]=read();

	int ans=0;
	for ( int i=n; i; i-- )
	{
		if ( i<=n-2 ) bmax( ans,Get(a[i]) );
		Add( a[i],20 );
	}

	printf("%d\n",ans );

	return 0;
}

Compatible Numbers

問數(shù)組中的每個(gè)數(shù) \(a[i]\) 是否可以在數(shù)組里面找到 \(a[j]\&a[i]=0\) ，輸出 \(a[j]\) 或 -1 .

也就是找 \(a[i]\) 取反之后的子集。

//Author: RingweEH
int main()
{
    memset( dp,-1,sizeof(dp) );
    n=read();
    for ( int i=1; i<=n; i++ ) a[i]=read(),dp[a[i]]=a[i];

    int lim=(1<<22);
    for ( int i=0; i<=22; i++ ) 
        for ( int S=0; S<lim; S++ )
            if ( dp[S]==-1 && (S>>i&1) ) dp[S]=dp[S^(1<<i)];

    for ( int i=1; i<=n; i++ ) printf("%d ",dp[(lim-1)^a[i]] );

    return 0;
}

動態(tài)DP(DDP)

前置芝士：

矩陣乘法加速遞推
一定的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（線段樹、樹剖、LCT……）

廣義矩陣乘法

DDP 的基本思想是把DP轉(zhuǎn)移式拆成矩陣乘法，然后再用數(shù)據(jù)結(jié)構(gòu)維護(hù)。很多DP式里面都有 \(\max\) ，無法用一般的加法乘法表達(dá)，所以我們需要對矩陣乘法進(jìn)行魔改。

矩陣乘法的結(jié)合律的成立只依賴于乘法對加法有分配率，\(a\cdot(b+c)=ab+ac\) ，而加法對 \(\min\max\) 也有分配率，\(a+\max(b,c)=\max(a+b,a+c)\) ，所以可以重定義矩陣乘法：\(C[i][j]=\max_k\{A[i][k]+B[k][j]\}\) ，發(fā)現(xiàn)這個(gè)新的矩乘很像 Floyd ，而 Floyd 的原理又是DP……所以？

引例 - SP1716

\(n\) 個(gè)數(shù)，\(q\) 次操作。

0 x y \(a[x]\) 修改為 \(y\)
1 l r 詢問 \([l,r]\) 最大子段和。

首先列出最大子段和的DP式：設(shè) \(f[i]\) 表示以 \(a[i]\) 結(jié)尾的最大子段和，\(g[i]\) 表示 \([1,i]\) 的最大子段和。

\[f[i]=\max(f[i-1]+a[i],a[i]),g[i]=\max(g[i-1],f[i]) \]

把這玩意兒改寫成矩陣乘法：

\[\begin{bmatrix} a_i & -\infin & a_i\a_i & 0 & a_i\-\infin & -\infin & 0 \end{bmatrix} \begin{bmatrix} f_{i-1}\g_{i-1}\0 \end{bmatrix} =\begin{bmatrix} f_i\\g_i\\0 \end{bmatrix} \]

線段樹維護(hù)區(qū)間矩陣乘積即可。

//Author: RingweEH
#define ls pos<<1
#define rs pos<<1|1
const int N=5e4+10,INF=INT_MAX>>2;
struct Matrix 
{ 
    int mat[3][3]; 
    Matrix(){for(int i=0;i<=2;i++)for(int j=0;j<=2;j++)mat[i][j]=-INF;}
}tr[N<<2];
int a[N],n,q;
Matrix operator * ( const Matrix &A,const Matrix &B )
{
    Matrix res;
    for ( int k=0; k<=2; k++ )
        for ( int i=0; i<=2; i++ )
            for ( int j=0; j<=2; j++ )
                bmax( res.mat[i][j],A.mat[i][k]+B.mat[k][j] );
    return res;
}
void Pushup( int pos ) { tr[pos]=tr[ls]*tr[rs]; }
void Build( int pos,int l,int r )
{
    if ( l==r )
    {
        tr[pos].mat[0][0]=tr[pos].mat[0][2]=tr[pos].mat[1][0]=tr[pos].mat[1][2]=a[l];
        tr[pos].mat[1][1]=tr[pos].mat[2][2]=0; return;
    }
    int mid=(l+r)>>1;
    Build(ls,l,mid); Build(rs,mid+1,r); Pushup(pos);
}
void Modify( int pos,int l,int r,int x,int val )
{
    if ( l==r ) { tr[pos].mat[0][0]=tr[pos].mat[0][2]=tr[pos].mat[1][0]=tr[pos].mat[1][2]=val; return; }
    int mid=(l+r)>>1;
    (x<=mid) ? Modify(ls,l,mid,x,val) : Modify(rs,mid+1,r,x,val);
    Pushup(pos);
}
Matrix Query( int pos,int L,int R,int l,int r )
{
    if ( l<=L && R<=r ) return tr[pos];
    int mid=(L+R)>>1;
    if ( l<=mid && r>mid ) return Query(ls,L,mid,l,r)*Query(rs,mid+1,R,l,r);
    return ( l<=mid ) ? Query(ls,L,mid,l,r) : Query(rs,mid+1,R,l,r);
}

int main()
{
    n=read();
    for ( int i=1; i<=n; i++ ) a[i]=read();
    q=read();

    Build(1,1,n);
    while ( q-- )
    {
        int opt=read(),x=read(),y=read();
        if ( opt )
        {
            if ( x>y ) swap( x,y );
            Matrix res=Query( 1,1,n,x,y );
            printf("%d\n",max(res.mat[1][0],res.mat[1][2]) );
        }
        else a[x]=y,Modify(1,1,n,x,y);
    }

    return 0;
}

P4719 樹的最大權(quán)獨(dú)立集

給定一棵 \(n\) 點(diǎn)樹，\(m\) 次單點(diǎn)修改點(diǎn)權(quán)操作，每次操作之后求最大權(quán)獨(dú)立集權(quán)值大小。

先不帶修改找式子。顯然是

\[f[u][0]=\sum_{v\in son[u]}\max(f[v][0],f[v][1])\\\f[u][1]=\sum_{v\in son[u]}f[v][0]+a[i] \]

然后，考慮要套什么數(shù)據(jù)結(jié)構(gòu)。由于這里復(fù)雜度要求是 \(\mathcal{O(n\log n)}\) ，所以不難想到用重鏈剖分。~~然而我貌似有點(diǎn)忘了~~

樹剖復(fù)習(xí)。

其實(shí)就是按照子樹大小劃分輕重兒子/邊，然后輕重鏈取極長，重節(jié)點(diǎn)優(yōu)先遍歷出來的DFS序中重鏈、子樹都是連續(xù)的。而且有重要性質(zhì)：任何一個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑中，包含不超過 \(\log n\) 條重鏈。

找重兒子和DFS序可以兩遍完成。后面就是在DFS序上維護(hù)東西了，沒什么好說的。

為了能樹剖，要把DP式子稍微修改一下：令 \(g[u][0]\) 表示 \(u\) 所有輕兒子，隨意取的最大權(quán)獨(dú)立集；\(g[u][1]\) 表示 \(u\) 所有輕兒子不取自己的最大值，加上 \(u\) 本身的權(quán)值。轉(zhuǎn)移方程就可以把求和去掉，變成（這里 \(v\) 是重兒子）

\[f[u][0]=\max(g[u][0]+f[v][0],g[u][0]+f[v][1])\\\f[u][1]=g[u][1]+f[v][0] \]

然后就要把它寫成矩陣：

\[\begin{bmatrix} g[u][0] & g[u][0]\g[u][1] & -\infin \end{bmatrix} \begin{bmatrix} f[v][0]\f[v][1] \end{bmatrix} = \begin{bmatrix} f[u][0]\f[u][1] \end{bmatrix} \]

為了節(jié)省空間把一些常見結(jié)構(gòu)體省略了……

//Author: RingweEH
void bmax( int &a,int b ) { a=(a>b) ? a : b; }
#define ls pos<<1
#define rs pos<<1|1
const int N=1e5+1,M=2e5+1,NM=4e5+1,INF=0x3f3f3f3f;
int tot,head[N],n,m,tim,f[N][2];
int a[N],fa[N],siz[N],dep[N],dfn[N],id[N];
int wson[N],top[N],ed[N];
struct Matrix
{
    int mat[2][2];
    Matrix(){memset(mat,-0x3f,sizeof(mat));}
}val[N];
Matrix operator * ( Matrix A,Matrix B )
struct Edge { int to,nxt; }e[M];
void Adde( int u,int v )
struct SegmentTree { int le[NM],ri[NM]; Matrix tr[NM]; }Tr;

void DFS1( int u )
{
    siz[u]=1;
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to;
        if ( v==fa[u] ) continue;
        fa[v]=u; dep[v]=dep[u]+1; DFS1(v);
        siz[u]+=siz[v];
        if ( siz[v]>siz[wson[u]] ) wson[u]=v;
    }
}

void DFS2( int u,int lin )
{
    id[u]=++tim; dfn[tim]=u; top[u]=lin; bmax(ed[lin],tim);
    f[u][0]=0; f[u][1]=a[u];
    val[u].mat[0][0]=val[u].mat[0][1]=0; val[u].mat[1][0]=a[u];
    if ( wson[u]^0 )
    {
        DFS2(wson[u],lin);
        f[u][0]+=max(f[wson[u]][0],f[wson[u]][1] ); f[u][1]+=f[wson[u]][0];
    }
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to;
        if ( v==fa[u] || v==wson[u] ) continue;
        DFS2(v,v);
        f[u][0]+=max(f[v][0],f[v][1]); f[u][1]+=f[v][0];
        val[u].mat[0][1]=val[u].mat[0][0]+=max(f[v][0],f[v][1]);
        val[u].mat[1][0]+=f[v][0];
    }
}

void Update( int x,int y )
{
    val[x].mat[1][0]+=y-a[x]; a[x]=y;
    Matrix pre,las;
    while ( x^0 )
    {
        pre=Tr.Query(1,id[top[x]],ed[top[x]]);
        Tr.Modify(1,id[x]);
        las=Tr.Query(1,id[top[x]],ed[top[x]]);
        x=fa[top[x]];
        val[x].mat[0][0]+=max(las.mat[0][0],las.mat[1][0])-max(pre.mat[0][0],pre.mat[1][0]);
        val[x].mat[0][1]=val[x].mat[0][0]; val[x].mat[1][0]+=las.mat[0][0]-pre.mat[0][0];
    }
}

int main()
{
    n=read(); m=read();
    for ( int i=1; i<=n; i++ ) a[i]=read();
    for ( int i=1,u,v; i<n; i++ ) u=read(),v=read(),Adde(u,v),Adde(v,u);

    DFS1(1); DFS2(1,1);
    Tr.Build(1,1,n); Matrix ans;
    for ( int i=1,x,y; i<=m; i++ )
    {
        x=read(); y=read();
        Update(x,y); ans=Tr.Query(1,id[1],ed[1]);
        printf("%d\n",max(ans.mat[0][0],ans.mat[1][0]) );
    }

    return 0;
}

NOIP2018 保衛(wèi)王國

看這里

參考材料

sosDP DDP

本站是提供個(gè)人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自：路人甲Java > 《待分類》

舉報(bào)/認(rèn)領(lǐng)