AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

2020年1月XX日状态压缩动态规划讲义

作者: 作者的头像   秦淮岸灯火阑珊 ,  2019-10-25 22:11:47 ,  所有人可见 ,  阅读 1403


6


4

导言

目前还有一些题目没有补充完整.

题目描述

某山贼集团在绿荫村拥有强大的势力,整个绿荫村由$N$个连通的小村落组成,并且保证对于每两个小村落有且仅有一条简单路径相连。

小村落用阿拉伯数字编号为$1,2,3,4, \dots ,n$,山贼集团的总部设在编号为$1$的小村落中。

山贼集团除了老大坐镇总部以外,其他的$P$个部门希望在村落的其他地方建立分部。

$P$个分部可以在同一个小村落中建设,也可以分别建设在不同的小村落中。每个分部到总部的路径称为这个部门的管辖范围,于是这$P$个分部的管辖范围可能重叠,或者完全相同。

在不同的村落建设不同的分部需要花费不同的费用。每个部门可能对他的管辖范围内的小村落收取保护费,但是不同的分部如果对同一小村落同时收取保护费,他们之间可能发生矛盾,从而损失一部分的利益,他们也可能相互合作,从而获取更多的利益。

现在请你编写一个程序,确定$P$个分部的位置,使得山贼集团能够获得最大的收益。

输入格式

输入文件第一行包含一个整数$N$和$P$,表示绿荫村小村落的数量以及山贼集团的部门数量。

接下来$N-1$行每行包含两个整数$X$和$Y$,表示编号为$X$的村落与编号为$Y$的村落之间有一条道路相连。($1 \le X,Y \le N$)

接下来$N$行,每行$P$个正整数,第$i$行第$j$个数表示在第$i$个村落建设第$j$个部门的分部的花费$A_{i,j}$。

然后有一个正整数$T$,表示下面有$T$行关于山贼集团的分部门相互影响的代价。($0 \le T \le 2 \times p$)

最后有$T$行,每行最开始有一个数$V$,如果$V$为正,表示会获得额外的收益,如果$V$为负,则表示会损失一定的收益。

然后有一个正整数$C$,表示本描述涉及的分部的数量,接下来有$C$个数,$X_i$,为分部门的编号($X_i$不能相同)。

表示如果$C$个分部$X_i$同时管辖某个小村落(可能同时存在其他分部也管辖这个小村落),可能获得的额外收益或者损失的收益为的$|V|$。

$T$行中可能存在一些相同的$X_i$集合,表示同时存在几种收益或者损失。

输出格式

输出文件要求第一行包含一个数$Ans$,表示山贼集团设置所有分部后能够获得的最大收益。

输入输出样例

输入 #1
2 1
1 2
2 
1
1
3 1 1
输出 #1
5

说明/提示

对于$40%$的数据,$1 \le P \le 6$。

对于$100%$的数据,$1 \le N \le 100$,$1 \le P \le 12$,保证答案的绝对值不超过${10}^8$。

解题报告

算法解析

剖析题意

首先我们分析题意,这道题目其实给了很多关键性的信息,我们可以提取

  1. 树上结构
  2. 每一个部门有着二进制状态,可以选择,或者不可以选择

  3. 数据范围特别小

综上所述,我们不难发现,这道题目与,树型DP,状压DP有着很大的联系.


状压设置

不难设置出,我们应该以$p$进行状压.

  1. 唯独他,范围小
  2. 分部门的总数

总而言之,状态设计为如下.
$$ S:每一个分部门是否选择 $$
.假如说
$$ S=1101 $$
那么表示为,选择,$1,3,4$这三个分部门


价值定义

我们发现,题目给出的一个关键地方为,不同分部门之间存在影响

既然如此,我们不妨思考一下,对于每一个状态,他们肯定有一个权值.

而这个权值,必然就是若干个分部门同时选择,产生的价值.

举个栗子
$$ 1,3分部门选择,价值为5 $$
然后.
$$ 1,4分部门选择,价值为-3 $$
现在我们选择的状态为.
$$ S=1101 $$
那么请问这个状态,它是什么价值呢?
$$ val[S]=5-3=2 $$
因此对于这类状态,我们显然是要存储下来他们的价值的.
$$ val[S]表示S状态的价值 $$


树型阶段

现在我们这个状态是出现了,但是阶段还没有划分好.

其实树型DP的阶段是最好划分的.

因为它的阶段就是以,父子节点作为分段.

既然如此,我们设计一下.
$$ f[i][S]表示在以i为根的子树里,分部门选择状态为S的最大收益 $$
那么这样,我们的状态表示就设置完毕了.


状态转移

状态已经设置完毕,我们现在缺失的就是动态规划的状态转移.

我们先来思考一些问题.

  1. 对于一个集合,它会被那些集合转移过来呢?

换句话说,就是有哪些符合条件的$S’$满足下面这个条件
$$ S’ => S $$
我们发现.
$$ S’ \in S $$
也就是说,$S’$是$S$的子集

  1. 从一个集合转移到另外一个集合,代价为什么

我们需要回顾一下定义.
$$ val[S]表示S状态的价值 $$
那么既然如此,一个集合状态它的代价,不就是.
$$ val[S] $$
这就是转移的代价,从一个状态到另外一个状态

  1. 树上怎么转移

①从儿子节点到父亲节点.

②从子集到当前集合

所以说我们的表达为
$$ f[x][S]=f[x][s’]+f[son[x]][S \oplus S’] $$
但是对于这个状态表示而言,我们的类型是最大价值,而且一个点有很多个儿子节点

一个节点只能从一个儿子节点转移过来,那么这个儿子必须是价值最高的.

所以变成了.
$$ f[x][S]=max(f[x][s],f[x][s’]+f[son[x]][S \oplus S’]) $$
之前当前节点的状态集合为$S’$,现在通过儿子上来的转移,现在变成了$S$

那么
$$ f[x][S]+=val[s] $$
然后我们分析上面这些语句.

不难发现,这个和背包问题特别相像

因此,这个转移就是树上背包转移

于是这道题目就是非常有趣的,动态规划算法大杂烩
$$ 背包DP+状压DP+树型DP=状态转移+状态设计+阶段转移 $$


代码解析

//本题目的算法为,背包DP+树型DP+状压DP,是一道DP的优秀题目
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))//x的最靠右边的1 
const int N=110,S=(1<<12)+3;
int n,p,M,t,a[N][N],f[N][S],val[S];
vector<int> g[N];
inline int tot(int x)//统计x二进制表示下的位数
{
    int cnt=0;
    while(x)
    {
        cnt++;
        x>>=1;
    }
    return cnt;
}
void dfs(int x,int fa)
{
    for(int y:g[x])
    {
        if (y==fa)//防止遍历回到曾经访问过的节点
            continue;
        dfs(y,x);//访问儿子节点,自下往上的转移,这是树型DP的精华
        for(int s=M; s; s--)//遍历所有集合,类似于背包问题的j,从M~1.
            for(int t=s; t; t=t=(t-1)&s)//从子集转移过来
                f[x][s]=max(f[x][s],f[x][s^t]+f[y][t]);//相当于加入第y个物品,它的体积是t
        //也可以认为是 t->s的一种转移
    }
    for(int s=0; s<=M; s++)//遍历所有集合
        f[x][s]+=val[s];//加上这个状态,分部门该有的影响
}
inline void init()
{
    scanf("%d%d",&n,&p);
    M=(1<<p)-1;//所有分部门都安排好该有的状态表示
    for(int i=1; i<n; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v),g[v].push_back(u);//这里是添加边,以无向图的方式存储
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=p; j++)
            scanf("%d",&a[i][j]);
        for(int j=1; j<=M; j++)
            f[i][j]=f[i][j ^ lowbit(j)]-a[i][tot(lowbit(j))];
        //在这里lowbit(j)为j的第一个是1的位置.tot(lowbit(j))这个1所在的位置
    }
    scanf("%d",&t);
    while(t--)
    {
        int v,c,x=0,s=0;
        scanf("%d%d",&v,&c);
        for(int i=1; i<=c; i++)
            scanf("%d",&x),s|=(1<<(x-1));//s表示本次操作收到影响分部门集合
        int p=s^M;//取出所有不受影响的位置
        for(int t=p; t; t=(t-1)&p)
            val[(t|s)]+=v;//所有包含s的集合,都要+v的影响
        val[s]+=v;//完全包含也要+v
    }
    dfs(1,0);
    printf("%d\n",f[1][M]);//1是根节点,M为所有分部门都安排好了,这就是最后的答案
}
signed main()
{
    init();
    return 0;
}

10 评论


用户头像
一念花开   2020-06-29 21:03         踩      回复

这个题目编号是多少了


用户头像
ChinaPie   2019-10-25 22:48         踩      回复

orz

用户头像
秦淮岸灯火阑珊   2019-10-26 17:19         踩      回复

STO


用户头像
Celina   2019-10-25 22:25         踩      回复

%%%

用户头像
秦淮岸灯火阑珊   2019-10-26 17:19         踩      回复

tql


用户头像
墨染空   2019-10-25 22:20         踩      回复

%%

用户头像
秦淮岸灯火阑珊   2019-10-26 17:19         踩      回复

捕捉大佬!

用户头像
墨染空   2019-10-28 20:46    回复了 秦淮岸灯火阑珊 的评论         踩      回复

时间咋变成1月份了233

用户头像
秦淮岸灯火阑珊   2019-10-29 19:51    回复了 墨染空 的评论         踩      回复

近期CSP过于忙碌啊

用户头像
墨染空   2019-10-29 19:51    回复了 秦淮岸灯火阑珊 的评论         踩      回复

qaq


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息