首师大附中集训D7日报（20231216）-总结部分

今天讲dp，切题9/28，dp是一个庞杂的，成体系的知识，因此今日总结不以题解为主，而以知识点和涉及到的例题为主，题解参考笔记和ppt

DP

1.背包问题

都到了这个层次了背板子不可能有问题，主要是对于背包问题本质的理解。

背包问题的转移说白了就是最普通的线性转移，并且是表现出无序性的，比如这道题：

消失之物

虽然是黄题，但是好题，涉及到一次背包后，多次对某些物品的查询，做法并不单一

• 因为背包问题状态转移有无序性，所以可以先正常跑，把当前排除的物品视作最后做出贡献的物品，这样就可以直接把这个物品的贡献反向跑一边，排除他的贡献，总复杂度n^2

	for(int i=1;i<=n;i++){
		memcpy(g,f,sizeof f);
		for(int j=w[i];j<=m;j++) g[j]=(g[j]-g[j-w[i]]+10)%10;
		for(int j=1;j<=m;j++) cout<<g[j]%10;
		cout<<"\n";
	}

• 可以把背包保留二位状态，然后从前向后从后向前各跑一次，排除一个物品或一个区间的物品时可以直接把剩余部分合并，总复杂度还是n^2 但是空间复杂度也变成了n^2，限制更强。

  不过这种做法允许排除一个区间的物品，而且通用于许多其他线性dp问题

如果出现背包问题作为考点，肯定是混合背包类型或配合特殊性质，也有树背包作为统计答案的出现情况

背包计数

并不是一道普通的背包问题，看起来是多重背包，但是这个复杂度显然不符合n*2

观察发现，本题的性质十分不一般，数量较多，体积较大的可视作完全背包，发现阈值为根号n，考虑根号分治，前根号n个采用前缀和优化多重背包，后面的把操作转化为增加一个根号n的体积或整体+1

m=sqrt(n);
   f[0][0]=1;
   for(i=1;i<=m;i++){
   	for(j=0;j<i;j++){
   		int cnt=0;
   		for(k=j;k<=n;k+=i){
   			cnt++;
   			sumf[cnt]=(sumf[cnt-1]+f[i-1][k])%mod;
   		}
   		for(k=j,l=1;k<=n;k+=i,l++) f[i][k]=((f[i][k]+sumf[l])%mod-sumf[max(0,l-1-i)]+mod)%mod;
   	}
   }
   g[0][0]=sumg[0]=1;
   for(i=1;i<=m;i++){
   	for(j=0;j<=n;j++){
   	    if(j>=i) g[i][j]=(g[i][j]+g[i][j-i])%mod;
   		if(j>=m+1) g[i][j]=(g[i][j]+g[i-1][j-(m+1)])%mod;
   		sumg[j]=(sumg[j]+g[i][j])%mod;
   	}
   }

2.区间dp，非常熟悉，注意刷表法和填表方法对复杂度和实现的影响

很多时候，区间dp的复杂度允许涉及l，r以外的状态维度

成绩单

状态设计题，在左右界的基础上，增加两个维度维护当前区间在已经消掉一部分之后的max和min用于继续转移，能想到这里这题差不多a了

for(int len=1;len<=n;len++){
		for(int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			for(int mn=1;mn<=n;mn++){
				for(int mx=1;mx<=n;mx++){
					if(w[mn]>w[mx]) continue;
					int &g1=g[l][r][mn][mx];
					for(int k=l;k<r;k++)
					g1=min(g1,g[l][k][mn][mx]+f[k+1][r]);
					int &g2=g[l][r+1][w[mn]<w[r+1]? mn:(r+1)][w[mx]>w[r+1]? mx:(r+1)];
					g2=min(g1,g2);

					f[l][r]=min(g1+a+b*(w[mn]-w[mx])*(w[mn]-w[mx]),f[l][r]);
				}
			}
		}
	}

add and remove

也是状态设计题，首先分析发现答案和元素贡献次数有关，新增两个维度维护当前区间向左右两侧的贡献

int f(int l,int r,int fl,int fr){
	if(r-l<=1) return 0;
	int  ans=INF64;
	for(int i=l+1;i<=r-1;i++)
		ans=min(ans,f(l,i,fl,fl+fr)+f(i,r,fl+fr,fr)+w[i]*(fl+fr));
	return ans;
}

其实这题状态不会重复，直接用dfs维护

Pairing points

这题同时在状态设计上和转移设计上有考察

首先不要被树的那个条件骗了，应该转化为之间不构成环，然后发现在已连一边后，可以在左右分别枚举左右连边的点，然后类似于分治的思路，向下继续配对

这个题很有难度了，状态设计与转移都不很明显的话，就需要认真分析了

int dp(int l,int k,int r){
	if((l^r)&1) return 0;
	if(l==k&&r==k) return 1;
	if(r==k||l==k) return 0;
	if(v[l][k][r]) return f[l][k][r];
	for(int p=l;p<k;p++)
		for(int q=r;q>k;q--)
			if(g[p][q]) 
				for(int x=p;x<k;x++)
					for(int y=q;y>k;y--)
					 f[l][k][r]+=dp(l,p,x)*dp(y,q,r)*dp(x+1,k,y-1);
	v[l][k][r]=1;
	return f[l][k][r];
}

3.数位dp

不要被骗了，其实就是普通的dp，正常理解限制条件，按位dp即可

注意设置lim值对数字大小进行限制，除此之外没什么特殊的了

模板题

int dfs(int pos,int pre,int st,int lim){
	if(pos>len) return 1;
	if(!lim&&f[pos][pre]!=-1) return f[pos][pre];
	int t=0;
	int res=9;
	if(lim) res=a[len-pos+1];
	for(int i=0;i<=res;i++){
		if(abs(i-pre)<2) continue;
		if(st&&i==0) t+=dfs(pos+1,-2,1,lim&&i==res);
		else t+=dfs(pos+1,i,0,lim&&i==res);
	}
	if(!lim&&!st) f[pos][pre]=t;
	return t;
}

除了板子还没有做几道题呢，回头更新

4.树上dp

Complete Compress

暴力思想：枚举每个点作为根，尝试枚举移动方法，复杂度在 $ n!$
级别上，还是别想了

改进思路：枚举根节点可以保留，思考如何用树形dp维护移动的过程。发现移动过程可以分直链曲链两种情况，一种会使两个点向LCA各自移动一条边，深度各自+1，还有一种会使两个点向中间深度移动一个深度+1一个深度-1

如果想到了这里，就应该考虑维护棋子（相对于子树的根节点）深度和 $size_u=∑dis_{u,v} $ ，v是u子树上的棋子，到这里可以判断是否有解了：两种移动情况会使 $size_{rt}$ 不变或+2，如果 $size_{rt}$ 为奇数，可以直接排除

但是要确定能否消完，现有的维护量不够用。直接维护答案：u子树内操作能达成的最小 $dis$ 值为 f，思考如何转移：一个子树在满足前一限制条件的情况下，无法把棋子消完，只可能是某一子树棋子过多，把全部棋子拉到了一棵子树上面

对于已经完成了子树内操作的子树v，其他子树上都可以用棋子的原始状态和它进行操作，可以在v点处全部消掉（有解情况下），但是v内部已经达到了最优，因此 $f_v$ 与其余dis的差即为结果，贪心可以证明正确，枚举v即可。

进一步优化，换根dp，对于以某个点为根求dep和的题型，可以换根dp。

对于size数组换根时的维护，显然除了换根的两个节点，其他子树都不受影响，直接把原根的数值转移给现在的根即可

对于f数组换根时的维护，仍然有除了换根节点外其他子树不受影响，因此只对根节点操作即可

开摆了，不想打换根dp了

剩下的树dp题等我慢慢做

5.动态规划优化

1）单调队列，单调栈优化，经典优化，思路很简单，但是看出来不容易

当状态转移在区间内最值转移或者有单调的转移关系，且l，r单调不减时，考虑使用单调数据结构

为了保证查询区间单调，可以采用离线搭配

因为具有单调性，可以考虑分治类算法，把一个n变成log

2）凸包优化 其实是斜率单调，用可并堆维护斜率的转折点或者平衡树维护所有的斜率

这个以后补例题把，等我把数据结构补一补……

3）数据结构优化，区间各种操作都可以用分治数据结构维护（或者块状数据结构维护抽象操作）

4） 斜率优化 将dp看做函数，用直线截函数图像

5）决策单调性 完全没有理解，只知道很厉害

优化这里留待补充