线性动态规划

树型动态规划（Tree DP）

专门用于解决树结构的优化问题，推导过程可能选择DFS

1、状态：根据树上的每个节点（边）的状态来定义，可能求最佳路径或最大独立集

2、方程：通过子结点的状态推导父节点的状态，考虑一定的约束条件

3、边界：叶子结点或者一些特殊情况，需要直接给出状态值

4、推导过程：DFS，递推，记忆化搜索等方案

最大独立集：

给定一棵树，求顶点的子集，使得在这个子集中任意两个顶点不直接相连，使这个子集的大小最大。

状态：对于顶点node

   dp[node][0]代表不选node结点时，最大独立集的大小

   dp[node][1]代表选node结点时，最大独立集的大小

方程：child为node的子结点

   dp[node][0]=sum(max(dp[child][0],dp[child][1]));

   dp[node][1]=1+sum(dp[child][0]);

边界：leaf叶子结点

   dp[leaf][0]=0;

   dp[leaf][1]=1;

结果：max(dp[root][0],dp[root][1]);

最小支配集：

给定一棵树，求顶点的子集，使得在这个子集所有能兼顾的点加起来覆盖整棵树，且这个子集的大小最小

状态：对于顶点node

   dp[node][0]父节点支配，子集大小的最小值

   dp[node][1]子节点支配，子集大小的最小值

   dp[node][2]自己支配，子集大小的最小值

方程：child为node的子结点

   dp[node][0]=sum(min(dp[child][1],dp[child][2]));

   dp[node][2]=sum(min(dp[child][0],dp[child][1],dp[child][2]);

   k=sum(min(dp[child][1],dp[child][2]));

   dp[node][1]=min(k-min(dp[child][1],dp[child][2])+dp[child][2]));

边界：leaf叶子结点

   dp[leaf][1]=最大值

   dp[leaf][2]=1;

结果：min(dp[root][1],dp[root][2])

1579题，完成输入，存储为邻接表。

int node[2000];

vector<int> e[2000];

int n,num,k,m,r;

int main(){

   cin>>n;

   for(int i=1;i<=n;i++){

       cin>>num>>k>>m;

       node[num]=k;

       for(int j=1;j<=m;j++){

           cin>>r;

           e[num].push_back(r);

           e[r].push_back(num);

       }

   }

   dfs(1,0);

   cout<<min(dp[1][1],dp[1][2]);

   return 0;

}

树型推导过程

int dp[2000][3];

void dfs(int u,int p){

   dp[u][2]=node[u];

   int sum=0;

   for(int i=0;i<e[u].size();i++){

       int v=e[u][i];

       if(v==p) continue;

       dfs(v,u);

       dp[u][0]+=min(dp[v][1],dp[v][2]);

       dp[u][2]+=min(min(dp[v][0],dp[v][1]),dp[v][2]);

       sum+=min(dp[v][1],dp[v][2]);

   }

   dp[u][1]=99999999;

   for(int i=0;i<e[u].size();i++){

       int v=e[u][i];

       if(v==p) continue;

       dp[u][1]=min(sum-min(dp[v][1],dp[v][2])+dp[v][2],dp[u][1]);

   }

}