2025/2/22课堂记录

目录

• 愚蠢的矿工
  
• 国王（猛兽军团）
  

• 愚蠢的矿工
  

这网页稍微有点乱，不过凑合凑合还能看，就是没法提交了而已
首先看到的第一眼，感觉是树上依赖背包
毕竟要挖到某一个节点的宝藏要之前知道根节点所有节点都要有狗狗停留
但是呢……
没错，他就是树上依赖背包（别打我）
但是呢，这道题还有第二种写法，就是多叉树转二叉树
没错，左牵儿子，右擎兄弟的孩子兄弟表示法

记住一个口诀：之前你的儿子现在是我的兄弟，现在你的儿子是我 
然后就可以根据普通的树形dp来做啦
这是代码[code]#include#includeusing namespace std;int a[1010],leftt[1010],rightt[1010],vis[1010][110];int dp(int x,int m)//dp(a,b):求以a为根节点的子树，给b位矿工，求最大值，也就是vis[a] {        if(m==0)return 0;//不给人没法干活        if(vis[x][m]!=-1)return vis[x][m];//之前算过这个，剪枝        if(x==-1)return 0;//访问的节点不存在，sorry，the number you…        int ans=0;//终于剪完枝了         ans=dp(rightt[x],m);//自己没留人，孩子不能走。把所有人手都给自己的兄弟        for(int i=0;i>n>>m;//宝藏个数；旷工人数        for(int i=1;i>a;        for(int i=0;ix>>y;                rightt[y]=leftt[x];//之前你的儿子现在是我的兄弟                leftt[x]=y;//现在你的儿子是我         }        cout