备战蓝桥杯---动态规划的一些思想2

话不多说，直接看题：

1.换根DP：

我们肯定不能对每一个根节点暴力求，我们不妨先求f[1]，我们发现当他的儿子作为根节点时深度和为f[1]+(n-cnt[i])-cnt[i](cnt[i]表示以i为根的节点数），这样子两遍DFS即可，下面是AC代码：

#include<bits/stdc++.h> using namespace std; int n,x,y,cnt[1000020],dep[1000010]; long long f[1000010]; vector<int> edge[1000010]; void dfs1(int root,int fa){ cnt[root]=1; for(int i=0;i<edge[root].size();i++){ int w=edge[root][i]; if(w==fa) continue; dep[w]=dep[root]+1; dfs1(w,root); cnt[root]+=cnt[w]; } return; } void dfs2(int root,int fa){ for(int i=0;i<edge[root].size();i++){ int w=edge[root][i]; if(w==fa) continue; f[w]=f[root]+n-2*cnt[w]; dfs2(w,root); } return; } int main(){ cin>>n; for(int i=1;i<=n-1;i++){ scanf("%d%d",&x,&y); edge[x].push_back(y); edge[y].push_back(x); } dep[1]=0; dfs1(1,0); for(int i=1;i<=n;i++){ f[1]+=dep[i]; } dfs2(1,0); long long ans=f[1]; for(int i=2;i<=n;i++){ ans=min(ans,f[i]); } cout<<ans; }

2.数学问题的背包转化：

 

显然，我们要求的就是n个中的极大线性无关组，那么我们如何求？

只要一个数可以被比他小的组合表示出来，那么这个元素就可以删了。

如何实现？我们把每一个元素看成无穷个物品，我们判断一个元素是否可以被表示，就是看这个背包是否可以被塞满，因此变成了完全背包问题，下面是AC代码：

#include<bits/stdc++.h> using namespace std; int a[110],n,t,m; bool dp[25005]; bool cmp(int a,int b){ return a<b; } int main(){ cin>>t; while(t--){ cin>>n; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1,cmp); m=n; dp[0]=1; for(int i=1;i<=n;i++){ if(dp[a[i]]==1){ m--; continue; } for(int j=a[i];j<=a[n];j++){ dp[j]=dp[j-a[i]]||dp[j]; } } cout<<m<<endl; } }

3.水题记录位置

就是在中序遍历上找根，再变成两个区间，用区间DP即可。

那么我们如何记录前序遍历呢，直接放在一维数组实现起来比较麻烦，于是我们可以用root[i][j]来记录i--j中选的根，然后再递归下去即可。

下面是AC代码：

#include<bits/stdc++.h> using namespace std; int dp[40][40],n,a[40],root[40][40]; int f(int l,int r){ if(dp[l][r]>0) return dp[l][r]; if(l==r) return dp[r][r]=a[r]; if(l>r) return 1; int g=l; for(int i=l;i<=r;i++){ if(dp[l][r]<=a[i]+f(l,i-1)*f(i+1,r)){ dp[l][r]=a[i]+f(l,i-1)*f(i+1,r); g=i;} } root[l][r]=g; return dp[l][r]; } void print(int l,int r){ if(l==r){ cout<<l<<" "; return; } if(l>r) return; cout<<root[l][r]<<" "; print(l,root[l][r]-1); print(root[l][r]+1,r); return; } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; cout<<f(1,n)<<endl; print(1,n); }

4.从小入手+两遍DP：

我们不妨先看一块，我们令f[k][i][x]表示第k条木板，前x个格子刷i次的最大正确粉刷格子数。

对于第k条木板，易得转移方程：f[k][i][x]=max(f[k][i-1][p]+w[p+1][x])(w[i][j]表示i--j一次刷最多可以刷对的格子数）

这样子，我们就把每一条木板刷的所有情况求出来，问题就转化成了分组背包。

我们令g[i][j]表示前i个木板刷了j次正确格子。

g[i][j]=g[i-1][k]+f[i][j-k][m].

下面是AC代码：

#include<bits/stdc++.h> using namespace std; int n,m,t,a[60][60],f[55][2600][55],g[55][2600],ck0[55][55],ck1[55][55],ff[55][2600]; char x; int main(){ cin>>n>>m>>t; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf(" %c",&x); a[i][j]=x-'0'; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]==0){ ck0[i][j]=ck0[i][j-1]+1; ck1[i][j]=ck1[i][j-1]; } else{ ck1[i][j]=ck1[i][j-1]+1; ck0[i][j]=ck0[i][j-1]; } } } int x1,x2; for(int i=1;i<=n;i++){ for(int j=1;j<=t;j++){ for(int k=1;k<=m;k++){ for(int p=0;p<=k;p++){ x1=ck0[i][k]-ck0[i][p]; x2=ck1[i][k]-ck1[i][p]; f[i][j][k]=max(f[i][j][k],f[i][j-1][p]+max(x1,x2)); } } } } for(int i=1;i<=n;i++){ for(int j=1;j<=t;j++){ for(int k=0;k<=j;k++){ g[i][j]=max(g[i][j],f[i][k][m]+g[i-1][j-k]); } } } cout<<g[n][t]; }