上讲习题

AcWing 320

这个题是环形的，首先处理环就是再接一段。然后考虑本题的操作，发现这个题就是把一些东西合并到一起，每次都有一个代价，求代价的最大值，而且必须是连续的。这样刚好满足区间$dp$的要求，则本题可以用区间$dp$解。设$f_{i,j}$为$i$到$j$的区间内合并成一个的最大代价，因为$r_i=l_{i+1}$，则有状态转移方程$f_{i,j}=\max (f_{i,k}+f_{k+1,j}+a_i\times a_{k+1}\times a_{j+1})$。

#include<iostream> using namespace std; const int NN=204; int a[NN],f[NN][NN]; int main() { int n,ans=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i+n]=a[i]; } for(int s=1;s<=2*n-1;s++) for(int i=1;i<=n*2-s;i++) { int j=i+s; for(int k=i;k<j;k++) f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]); } for(int i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]); printf("%d",ans); return 0; }

AcWing 320

本题需要计算某个区间的价值和，首先知道肯定要前缀和求价值。能求价值了，接下来考虑，发现要把某个地方割开，这正好和区间$dp$找一个$k$分割出两个区间求最大值很像。于是，我们就只需要知道是哪个矩阵就可以枚举怎么切了。因为本题是二维的，所以要分别枚举横着或竖着切。设$f_{i1,j1,i2,j2,k}$表示矩阵的左上角和右下角的坐标以及还能切的次数，然后枚举在矩阵中怎么切割。因为本题状态十分混乱，所以最好记忆化搜索。以上就是二维的区间$dp$，二维$dp$中需要枚举横着和竖着的情况，分割出来的是两个矩阵。

#include<bits/stdc++.h> using namespace std; const int NN=9; int n,s[NN][NN]; double f[NN][NN][NN][NN][19]; double get(int x1,int y1,int x2,int y2) { double sum=(double)(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1])-1.0*s[8][8]/n; return sum*sum/n; } double dp(int x1,int y1,int x2,int y2,int k) { if(f[x1][y1][x2][y2][k]>=0) return f[x1][y1][x2][y2][k]; if(k==1) return get(x1,y1,x2,y2); f[x1][y1][x2][y2][k]=1e9; for(int i=x1;i<x2;i++) { f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],dp(x1,y1,i,y2,k-1)+get(i+1,y1,x2,y2)); f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],dp(i+1,y1,x2,y2,k-1)+get(x1,y1,i,y2)); } for(int i=y1;i<y2;i++) { f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],dp(x1,y1,x2,i,k-1)+get(x1,i+1,x2,y2)); f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],dp(x1,i+1,x2,y2,k-1)+get(x1,y1,x2,i)); } return f[x1][y1][x2][y2][k]; } int main() { scanf("%d",&n); for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) scanf("%d",&s[i][j]); for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; memset(f,-1,sizeof f); printf("%.3lf\n",sqrt(dp(1,1,8,8,n))); return 0; }

概念

树形$dp$，故名思意就是树上做$dp$。树形$dp$有普通的，还有换根$dp$是针对与无根树的。

方法

一般来说都是记忆化搜索。说好听点是记忆化搜索，但是因为树上每个节点都只能用一次，很多题和暴搜没什么区别。如果需要换根，则先找出一个虚拟根，计算该方案，然后每个节点都用父亲的方案和儿子的方案进行比较。所以第一次是算的儿子的方案，第二次搜下来一路存的是父亲的方案。

例题

AcWing 1073

这个题就是找树的直径。依次把每个点当作根，每次每个子树都计算到叶子的最长路径，然后最长的路径和次长的路径相加就是经过该点的直径。因为本题不关心根，则按理来说要换根。但是如果选择了向上的路径，则最上面的点还可以再选一条路径，则一定会更优。那么就只用求向下的路径，所以不用换根。

#include<bits/stdc++.h> using namespace std; vector<pair<int,int> >g[10004]; int ans; int dfs(int u,int fa) { int d=0,max1=0,max2=0; for(int i=0;i<g[u].size();i++) { int v=g[u][i].first; if(v==fa) continue; int sum=dfs(v,u)+g[u][i].second; d=max(d,sum); if(sum>max1) { max2=max1; max1=sum; } else if(sum>max2) max2=sum; } ans=max(ans,max1+max2); return d; } int main() { int n; scanf("%d",&n); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back({v,w}); g[v].push_back({u,w}); } dfs(1,0); printf("%d",ans); return 0; }

AcWing 1073

本题要求找一个点使得最远点的距离最短。和上一题的思路一样，每次找到儿子的最远距离，然后取个$\min$。但是本题并没有什么特殊性质，所以要换根。第二次计算向上的最长路径，即父亲的最长路径再加上这条边。但是父亲的最长路径有个能是从自己这里过去的，所以向上的最长路径就是父亲的次长路径。最后统计向上和向下哪个更大，作为这个点的最大长度，然后取$\min$就是答案。

#include<bits/stdc++.h> using namespace std; const int NN=10004; vector<pair<int,int> >g[NN]; int d1[NN],d2[NN],maxson[NN],p[NN]; int dfs1(int u,int fa) { for(int i=0;i<g[u].size();i++) { int v=g[u][i].first; if(v==fa) continue; int sum=dfs1(v,u)+g[u][i].second; if(sum>d1[u]) { d2[u]=d1[u]; d1[u]=sum; maxson[u]=v; } else if(sum>d2[u]) d2[u]=sum; } return d1[u]; } void dfs2(int u,int fa) { for(int i=0;i<g[u].size();i++) { int v=g[u][i].first; if(v==fa) continue; if(v==maxson[u]) p[v]=max(p[u],d2[u])+g[u][i].second; else p[v]=max(p[u],d1[u])+g[u][i].second; dfs2(v,u); } } int main() { int n; scanf("%d",&n); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back({v,w}); g[v].push_back({u,w}); } dfs1(1,0); dfs2(1,0); int ans=1e9; for(int i=1;i<=n;i++) ans=min(ans,max(d1[i],p[i])); printf("%d",ans); return 0; }

AcWing 323

这个题每个点可以选择放或者不放，所以可以用状态机解决。设$f_{i,(0,1)}$分别表示自己不用和用覆盖完本子树的最小代价。如果不用则所有儿子都要用，$f_{u,0}+=f_{v,1}$。如果用则所有儿子可以选择用或不用，$f_{u,1}+=\min (f_{v,0},f_{v,1})$，当然，别忘了加上自己这个点的贡献，$f_{u,1}++$。

#include<bits/stdc++.h> using namespace std; const int NN=1504; vector<int>g[NN]; int f[NN][5]; bool isson[NN]; int dp(int x) { f[x][0]=0; f[x][1]=1; for(int i=0;i<g[x].size();i++) { int v=g[x][i]; dp(v); f[x][0]+=f[v][1]; f[x][1]+=min(f[v][1],f[v][0]); } } int main() { int n,root=0; while(scanf("%d",&n)!=EOF) { for(int i=0;i<NN;i++) { isson[i]=false; g[i].clear(); } for(int i=1;i<=n;i++) { int x,y; scanf("%d:(%d)",&x,&y); for(int j=1;j<=y;j++) { int z; scanf("%d",&z); g[x].push_back(z); isson[z]=true; } } while(isson[root]) root++; dp(root); printf("%d\n",min(f[root][0],f[root][1])); } return 0; }

习题

AcWing 1075

AcWing 1074

AcWing 1077

解析和代码在下一篇博客——数位$dp$给出