DAG上dp

DAG上的dp一般有记忆化搜索与拓扑排序两种方法来实现。

食物链

食物链

两者时间复杂度都是线性的
拓扑排序解法：

#include <iostream>
#include <queue>

using namespace std;
const int N=1e5+5,M=2e5+5;
int n,m;
int head[N],to[M],nxt[M],cnt;   //链式前向星
int din[N],dout[N],deg[N],tim[N],ans;

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void topo() {   //拓扑排序
    queue<int> q;
    for(int i=1;i<=n;i++)   //把0入度点放入队
          if(!din[i]) {
              q.push(i);
              tim[i]=1;
        }
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i];
            if(deg[v]==0)
              continue;
            tim[v]+=tim[u]; //决策
            if(--deg[v]==0)
              q.push(v);
        }
    }
}

int main() {
    cin>>n>>m;
    while(m--) {
        int u,v;
        cin>>u>>v;
        add(u,v);
        deg[v]++;
        din[v]++;
        dout[u]++;
    }
    topo();
    for(int i=1;i<=n;i++)
      if(!dout[i] and din[i])   //无出度且不孤立
        ans+=tim[i];
    cout<<ans;
    return 0;
}

记忆化搜索解法

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+5,M=2e5+5;
int n,m;
int head[N],to[M],nxt[M],cnt;
int din[N],dout[N],tim[N],ans;

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

int dfs(int u) {
    if(tim[u]!=-1)
      return tim[u];    //记忆化
    if(dout[u]==0) {    //边界
        tim[u]=1;   //直接返回
        return 1;
    }
    tim[u]=0;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        tim[u]+=dfs(v); //决策
    }
    return tim[u];
}

int main() {
    cin>>n>>m;
    while(m--) {
        int u,v;
        cin>>u>>v;
        add(u,v);
        din[v]++;
        dout[u]++;
    }
    memset(tim,-1,sizeof(tim));
    for(int i=1;i<=n;i++)
      dfs(i);
    for(int i=1;i<=n;i++)
      if(!din[i] and dout[i])   //记忆化搜索过后，次数都在零入度点中，与拓扑排序不同，请仔细斟酌
        ans+=tim[i];
    cout<<ans;
    return 0;
}

空岛

空岛
同样，有拓扑排序和记忆化搜索两种解法，当然还有SPFA。
不过用SPFA解这题有点大材小用了，并且可能被卡常。
拓扑排序解法：

#include <bits/stdc++.h>

using namespace std;
const int N=1e6+5,M=4e6+5;
int n,m,s;
int a[N],dist[N],ans,deg[N];
int head[N],to[M],nxt[M],cnt;

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void topo() {
    queue<int> q;
    dist[s]=a[s];
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i];
            if(--deg[v]==0)
              q.push(v);
            dist[v]=max(dist[v],dist[u]+a[v]);  //类似于Dijkstra算法的决策
        }
        ans=max(dist[u],ans);
    }
}

int main() {
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
      cin>>a[i];
    while(m--) {
        int u,v;
        scanf("%d%d",&u,&v);
        deg[v]++;
        add(u,v);
    }
    topo();
    cout<<ans;
    return 0;
}

记忆化搜索更好写，并且常数小，这里代码不发了。

树形dp（旧文）

旧文原址
树形dp是一种在树上做的dp，通常的结构为：

void dp(int u) {
    vis[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        if(vis[v])
          continue;
        dfs(v);
        update(f[u],f[v]);  //用f[v]来更新f[u]
    }
}

先递归子节点，再从子节点向上转移，这样就是一般的树形dp。

树直径

考虑这样一道题：
给定一棵无根树，求两个距离最远的节点间的距离，两个相邻结点距离为1。
首先，两个距离最远的结点必定是“边界点”，即度为1的点。
我们不妨对于每个点，求出这个点到这个点的子树的所有边界点的最长距离与次长距离，设为f[x][1],f[x][2]，那么答案也就自然是$\max_{1\leq i\leq n}(f[i][1]+f[i][2])$
主要的瓶颈就在于：如何求出每个点的f呢？
我们看下dp代码

void dfs(int u) {
    v[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int y=to[i];
        if(v[y])    //已经访问过了（即父节点），跳过
          continue;
        dfs(y); //递归子节点
        //以下代码请好好斟酌
        if(h[u][1]<=h[y][1]+1) {    //如果最长路可以更新
            h[u][2]=h[u][1];    //将次长路更新为最长路
            h[u][1]=h[y][1]+1;  //将最长路更新为新值
        }
        else if(h[u][2]<=h[y][1]+1) //如果次长路可以更新
          h[u][2]=h[y][1]+1;    //更新次长路
    }
}

因为这个树是一个无根树，所以我们从任意一个点开始执行dfs都可以。

树上背包问题

CTSC1997 选课

题目链接：选课或acwing286
这n门课构成了一个森林的结构，为了简便，可以添加零号节点为各个树根的父亲，方便dp。
状态定义：f[u][t]表示在以u为根的子树中选t门的最高得分。
状态的转移实际上是一个分组背包模型，一个点的所有子节点看做是一组物品v，每组物品有f[v][i]的价值与i的消费。每组物品中只能取一个。

#include <iostream>
#include <cstring>

using namespace std;
const int N=3e2+5;
int n,m;
int head[N],to[N],nxt[N],cnt;
int score[N];
int f[N][N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}


void dp(int u) {
    f[u][0]=0;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        dp(v);
        for(int t=m;t>=0;t--)   //背包状态转移
          for(int j=t;j>=0;j--)
            f[u][t]=max(f[u][t],f[u][t-j]+f[v][j]);
    }
    if(u!=0)
      for(int i=m;i>0;i--)
        f[u][i]=f[u][i-1]+score[u];
}

int main() {
    memset(f,0xc0,sizeof(f));
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        int u;
        cin>>u>>score[i];
        add(u,i);
    }
    dp(0);
    cout<<f[0][m];
    return 0;
}

二叉苹果树

题目链接：二叉苹果树
有了上面一道题，这道题就更加简单了，直接看代码。
注意不同的是，这道题是边权，上一题是点权。

#include <iostream>
#include <cstring>

using namespace std;
const int N=3e2+5;
int n,m;
int head[N],to[N],val[N],nxt[N],cnt;
bool vis[N];
int f[N][N];

void add(int u,int v,int w) {
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void dp(int u) {
    vis[u]=true;
    f[u][0]=0;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i],w=val[i];
        if(vis[v])
          continue;
        dp(v);
        for(int t=m;t>=0;t--)
          for(int j=t;j>=0;j--)
            f[u][t]=max(f[u][t],f[u][t-j-1]+f[v][j]+w); //此处减一是要把自己算上去
    }
}

int main() {
    memset(f,0xc0,sizeof(f));
    cin>>n>>m;
    for(int i=1;i<n;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dp(1);
    cout<<f[1][m];
    return 0;
}

典型树形dp

没有上司的舞会

题目链接：没有上司的舞会或acwing285
状态定义：f[u][0]表示当u不选时，u的子树的最大值，f[u][1]表示选u时，u的最大值。
那么很容易写出状态转移方程了。

#include <iostream>
#include <cstdio>

using namespace std;
const int N=2e4+5;
int head[N],nxt[N],to[N],cnt;
int f[N][2],h[N],n,root,in[N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void dp(int p) {
    f[p][0]=0;
    f[p][1]=h[p];
    for(int i=head[p];i;i=nxt[i]) {
        int y=to[i];
        dp(y);  //这边要注意：如果有明确的依赖关系，就不需要判断是否为父亲，建边时建单向边即可。但是如果只是说有一条边，那么就要双向建边，并判断到达点是否为当前点的父亲
        f[p][0]+=max(f[y][1],f[y][0]);  //如果当前点不选，它的下级既可以选也可以不选
        f[p][1]+=f[y][0];   //如果当前点选，那么只有不选它的下级
    }
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>h[i];
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        add(v,u);
        in[u]++;    //记录入度，根的入度必定为0
    }
    for(int i=1;i<=n;i++)
      if(in[i]==0) {
        root=i;
          break;
      }
    dp(root);   //从根开始dp
    cout<<max(f[root][0],f[root][1]);   //选根与不选根取最大值
    return 0;
}

数字转换

题目链接：数字转换
看起来不像树形dp，但我们可以把它转化成数形dp
设一个数x的约数和叫d[x]，那么对于每个x我们不妨看做是x到d[x]连一条边。最后求这棵树的直径就行了。

#include <iostream>
#include <cstdio>

using namespace std;
const int N=4e5+5;
int n,m;
int head[N],to[N],nxt[N],cnt;
bool v[N];
int h[N][3],ans;
int sum[N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

//求直径传统艺能
void dfs(int u) {
    v[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int y=to[i];
        if(v[y]) 
          continue;
        dfs(y);
        if(h[u][1]<=h[y][1]+1) {
            h[u][2]=h[u][1];
            h[u][1]=h[y][1]+1;
        }
        else if(h[u][2]<=h[y][1]+1)
          h[u][2]=h[y][1]+1; 
    }
}

int main() {
    cin>>n;
    //求每个数的约数和并加边
    for(int i=1;i<=n;i++) { //枚举因子来求约数和
        if(sum[i]<i) {  //约数和小于原数
            add(i,sum[i]);  //加两条边
            add(sum[i],i);
        }
        for(int j=i*2;j<=n;j+=i)    //枚举i的倍数
          sum[j]+=i;
    }
    dfs(1);
    for(int i=1;i<=n;i++)
      ans=max(ans,h[i][1]+h[i][2]); //直径
    cout<<ans;
    return 0;
}

二次扫描与换根法

如果题目中要对每个点都进行统计，并且这棵树是无根树，那么就可以使用这个方法。
1、第一次扫描，任选一个点为根，执行从下到上的dp
2、第二次扫描，以刚才那个点为根，进行从上到下的推导
我们可以解决比如：求每个点到任意点的最长路，或者次长路等的问题。

Accumulation Degree

这道题目蓝书上面有讲解，就不赘述了。