Luogu P2607 [ZJOI2008]骑士

题目链接: https://www.luogu.org/problemnew/show/P2607

题目意思非常简单,给你一张图,然后图中不能选最大相邻点,最后最大的选中的点的权值

很容易想到 没有上司的舞会 这种树形 DP 题目,但是显然,这,并不是一棵树

根据题目可得,每一个人只会有一条出边,即,这张图中,一张节点个数为 $n$ 的联通块,会有 $n$ 条边

环套树没得跑了

即每一个联通块中一定有一条边,删掉后就是树了

设这条边为 $u – v$ 的边,则 $\max(f_{u,0}, f_{u,1})$ 就是这个联通块的答案

建双向边判环即可

至于代码中的 xor ,当反向边即可

继续阅读“Luogu P2607 [ZJOI2008]骑士”

Luogu P3174 [HAOI2009]毛毛虫

题目链接: https://www.luogu.org/problemnew/show/P3174

这应该是我第一次没看 sol 做紫题吧……

虽然个人感觉比大多数紫题简单许多

题目本质是要求最长链的,但是要求是带每个点周围点的

我们设每个点的点权是这个点的连接点个数减 1

然后求最长链

得出来的链的长度 +2 即为答案

可以理解为因为大多数点都有一条边要连出去防止重复计算而减一

但是这样链头链尾会没算上,所以加二

继续阅读“Luogu P3174 [HAOI2009]毛毛虫”

树形背包 — Luogu P1273 有线电视网

0x01 写在开头

题目链接:[https://www.luogu.org/problemnew/show/P1273]

前置技能 : 树形DP

如果做过选课的话,想必各位一看到就知道这是一道树形DP的题目

0x02 题目

题目中要求我们在以收入$\geq 0$的前提下,支持尽可能多的叶子节点

因此我们可以这么定义一个类似背包状态转移方程
$$
f(now,i+j)=max(f(now,i+j),f(son,j)+f(now,i)-val)
$$
这不就是背包吗<(=°д)ノ

边界条件
$$
f(i,j)=-INF(0\leq i \leq N,0 \leq j \leq M)
$$
设为$-INF$是为了防止无法转移

看起来很显然是吧

让我们来看看代码:

0x03 代码

#include <cstdio>
#include <cstring>
const int N=3100;
inline int Max(int a,int b){return a>b?a:b;}
int _case;
int ans,v,w,n,m,son[N];
int f[N][N];
// edge start
struct edge{
    int to,next,val;
}e[N];
int ehead[N],ecnt;
inline void add_edge(int now,int to,int val){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].val=val;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
// dfs start
void dfs(int now){
    if(now>n-m){// 只有用户才会算到叶子节点中
        son[now]=1;
        return ;
    }
    f[now][0]=0;
    for(int u=ehead[now];u;u=e[u].next){
        dfs(e[u].to);
        for(int i=son[now];i>=0;i--){
            for(int j=1;j<=son[e[u].to];j++){// 注意循环顺序,不这么循环会重复计算一些东西
                f[now][i+j]=Max(f[now][i+j],f[now][i]+f[e[u].to][j]-e[u].val);
            }
        }
        son[now]+=son[e[u].to];
    }
}
// dfs end
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-m;i++){
        scanf("%d",&_case);
        while(_case--){
            scanf("%d%d",&v,&w);
            add_edge(i,v,w);
        }
    }
    memset(f,-0x3f,sizeof(f));
    for(int i=1;i<=m;i++) scanf("%d",&f[n-m+i][1]);
    dfs(1);
    for(int i=1;i<=m;i++){
        if(f[1][i]>=0) ans=i;
    }
    printf("%d",ans);
}
]]>