洛谷 P1352 没有上司的舞会

树形 DP 模板题。

#include <bits/stdc++.h>
using namespace std;
const int N=6010;
struct node{
    int v,next;
}e[N];
int n,l,k,cnt;
bool v[N];
int head[N],f[N][2];
void DFS(int u){
    v[u]=true;
    for(int i=head[u];i;i=e[i].next){
        if(v[e[i].v]) continue; //一个员工可能不止一个直接上司
        DFS(e[i].v);
        f[u][0]+=max(f[e[i].v][0],f[e[i].v][1]);
        f[u][1]+=f[e[i].v][0];
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&f[i][1]);
    for(int i=1;i<=n-1;++i){
        scanf("%d%d",&l,&k);
        v[l]=true;
        e[++cnt].v=l;
        e[cnt].next=head[k];
        head[k]=cnt;
    }
    for(int i=1;i<=n;++i)
        if(!v[i]){
            memset(v,false,sizeof(v));
            DFS(i);
            printf("%d\n",max(f[i][0],f[i][1]));
            return 0;
        }
}

AcWing 10. 有依赖的背包问题

此题是背包型的树形DP。

AC 代码：

#include <iostream>
using namespace std;
const int N=110;
struct node{
    int v,next;
}e[N];
int n,c,p,cnt,root;
int v[N],w[N],head[N],f[N][N];
void DFS(int u){
    //先为u节点留个位置，然后枚举所有状态体积小于等于c-v[u]的所有子节点们能够获得的最大价值
    for(int i=head[u];i;i=e[i].next){
        DFS(e[i].v);
        for(int j=c-v[u];j>=0;--j)
            for(int k=0;k<=j;++k)
                f[u][j]=max(f[u][j],f[u][j-k]+f[e[i].v][k]);
    }
    //最后选上第u件物品
    for(int i=c;i>=v[u];--i) f[u][i]=f[u][i-v[u]]+w[u];
    for(int i=0;i<v[u];++i) f[u][i]=0; //清空没选上u的所有状态
}
int main(){
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;++i){
        scanf("%d%d%d",&v[i],&w[i],&p);
        if(p==-1) root=i;
        else{
            e[++cnt].v=i;
            e[cnt].next=head[p];
            head[p]=cnt;
        }
    }
    DFS(root);
    printf("%d\n",f[root][c]);
    return 0;
}

AcWing 1075. 数字转换

一道简单的模板题，其中求 f 的这一步是重点，最后转化为了求树的直径。

AC 代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string.h>
using namespace std;
const int N=5e4+10;
int n,f[N],d1[N],d2[N],ans;
vector<int>e[N];
void dfs(int u,int fa){
    for(int &v:e[u]){
        if(v==fa) continue;
        dfs(v,u);
        if(d1[v]+1>d1[u]) d2[u]=d1[u],d1[u]=d1[v]+1;
        else if(d1[v]+1>d2[u]) d2[u]=d1[v]+1;
    }
    ans=max(ans,d1[u]+d2[u]);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) f[i]=1;
    for(int i=2;i<=n;++i)
        for(int j=2;j*i<=n;++j)
            f[j*i]+=i;
    for(int i=2;i<=n;++i)
        if(f[i]<i){
            e[i].push_back(f[i]);
            e[f[i]].push_back(i);
        }
    dfs(1,1);
    printf("%d\n",ans);
    return 0;
}