洛谷P3354河流（树形dp）
题目链接：https://www.luogu.org/problem/show?pid=3354#sub
题解：还是深搜，因为能运输到的伐木场一定在村庄的下游（或本身），即伐木场一定是村庄的父节点（或本身），当我们访问到村庄时，下游的最近伐木场一定被决定出来了。
我们用dp(i,j,k)表示当前访问到了i这个点，最近的伐木场为j这个点，还可以再建k个伐木场,,s[i][j]表示点i到点j的距离，w[i]表示节点有几吨木材。
那么如果在当前节点间造伐木场的话
f[i][j][k]=min(f[i][j][k],f[son][i][p]+f[brother][j][k-p-1]);
如果不造的话
f[i][j][k]=min(f[i][j][k],f[son][j][p]+f[brother][j][k-p]+s[i][j]*w[i]);
有两点：1.记忆化搜索；2.多叉为二叉
具体写程序注释：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int w[500],d[500],n,f[500][500][100]; int lef[500],righ[500],son[500]; int dp(int from,int to,int k,int s) //s表示i到j的距离 { if (from==n+1) return 0; //如果没有节点了 if (f[from][to][k]!=-1) return f[from][to][k];//记忆化搜索 int now=2100000000; for (int i=0;i<=k-1;i++) now=min(now,dp(lef[from],from,i,0)+dp(righ[from],to,k-1-i,s)); for (int i=0;i<=k;i++) now=min(now,dp(lef[from],to,i,s+d[from])+dp(righ[from],to,k-i,s)+w[from]*(s+d[from])); f[from][to][k]=now; return now; } int main() { int k; scanf("%d%d",&n,&k); for (int i=0;i<=n;i++) { lef[i]=righ[i]=n+1; for (int j=0;j<=n;j++) for (int p=0;p<=k;p++) f[i][j][p]=-1; } int v; for (int i=1;i<=n;i++) { scanf("%d%d%d",&w[i],&v,&d[i]); if (son[v]) righ[son[v]]=i; else lef[v]=i; son[v]=i; //转为二叉树 } printf("%d\n",dp(lef[0],0,k,0)); return 0; }优质内容筛选与推荐>>
1、96. Unique Binary Search Trees
2、UTL_FILE包
3、Spring boot项目集成Neo4j
4、50个网页常用小代码
5、Postman：非专业的并发测试