口碑好的网站开发,网件路由器为什么都是官翻,wordpress如何显示分类目录,西安百度百科话不多说#xff0c;直接看题#xff1a; 1.换根DP#xff1a; 我们肯定不能对每一个根节点暴力求#xff0c;我们不妨先求f[1]#xff0c;我们发现当他的儿子作为根节点时深度和为f[1](n-cnt[i])-cnt[i](cnt[i]表示以i为根的节点数#xff09;#xff0c;这样子两遍DFS…话不多说直接看题 1.换根DP 我们肯定不能对每一个根节点暴力求我们不妨先求f[1]我们发现当他的儿子作为根节点时深度和为f[1](n-cnt[i])-cnt[i](cnt[i]表示以i为根的节点数这样子两遍DFS即可下面是AC代码
#includebits/stdc.h
using namespace std;
int n,x,y,cnt[1000020],dep[1000010];
long long f[1000010];
vectorint edge[1000010];
void dfs1(int root,int fa){cnt[root]1;for(int i0;iedge[root].size();i){int wedge[root][i];if(wfa) continue;dep[w]dep[root]1;dfs1(w,root);cnt[root]cnt[w];}return;
}
void dfs2(int root,int fa){for(int i0;iedge[root].size();i){int wedge[root][i];if(wfa) continue;f[w]f[root]n-2*cnt[w];dfs2(w,root);}return;
}
int main(){cinn;for(int i1;in-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 i1;in;i){f[1]dep[i];}dfs2(1,0);long long ansf[1];for(int i2;in;i){ansmin(ans,f[i]);}coutans;
} 2.数学问题的背包转化 显然我们要求的就是n个中的极大线性无关组那么我们如何求
只要一个数可以被比他小的组合表示出来那么这个元素就可以删了。
如何实现我们把每一个元素看成无穷个物品我们判断一个元素是否可以被表示就是看这个背包是否可以被塞满因此变成了完全背包问题下面是AC代码
#includebits/stdc.h
using namespace std;
int a[110],n,t,m;
bool dp[25005];
bool cmp(int a,int b){return ab;
}
int main(){cint;while(t--){cinn;memset(dp,0,sizeof(dp));for(int i1;in;i) scanf(%d,a[i]);sort(a1,an1,cmp);mn;dp[0]1;for(int i1;in;i){if(dp[a[i]]1){m--;continue;}for(int ja[i];ja[n];j){dp[j]dp[j-a[i]]||dp[j];}}coutmendl;}
}
3.水题记录位置 就是在中序遍历上找根再变成两个区间用区间DP即可。
那么我们如何记录前序遍历呢直接放在一维数组实现起来比较麻烦于是我们可以用root[i][j]来记录i--j中选的根然后再递归下去即可。
下面是AC代码
#includebits/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(lr) return dp[r][r]a[r];if(lr) return 1; int gl;for(int il;ir;i){if(dp[l][r]a[i]f(l,i-1)*f(i1,r)){dp[l][r]a[i]f(l,i-1)*f(i1,r);gi;}}root[l][r]g;return dp[l][r];
}
void print(int l,int r){if(lr){coutl ;return;}if(lr) return; coutroot[l][r] ;print(l,root[l][r]-1);print(root[l][r]1,r);return;
}
int main(){cinn;for(int i1;in;i) cina[i];coutf(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[p1][x])(w[i][j]表示i--j一次刷最多可以刷对的格子数
这样子我们就把每一条木板刷的所有情况求出来问题就转化成了分组背包。
我们令g[i][j]表示前i个木板刷了j次正确格子。
g[i][j]g[i-1][k]f[i][j-k][m].
下面是AC代码
#includebits/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(){cinnmt;for(int i1;in;i){for(int j1;jm;j){scanf( %c,x);a[i][j]x-0;}}for(int i1;in;i){for(int j1;jm;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 i1;in;i){for(int j1;jt;j){for(int k1;km;k){for(int p0;pk;p){x1ck0[i][k]-ck0[i][p];x2ck1[i][k]-ck1[i][p];f[i][j][k]max(f[i][j][k],f[i][j-1][p]max(x1,x2));}}}}for(int i1;in;i){for(int j1;jt;j){for(int k0;kj;k){g[i][j]max(g[i][j],f[i][k][m]g[i-1][j-k]);}}}coutg[n][t];
}
