标签-状压dp

题意在树上放一些山贼集团的分部,每个分部可以收取根节点到它路径上所有节点的保护费。在节点 $i$ 建立分部 $j$ 花费 $s[i][j]$ 。对于每一个节点,如果它被多个分部收保护费,就可能产生收益或损失。求最优的放置方法,可以得到最大利润。其中点数 $N\le 100$ ,分部个数 $P\le 12$ 。题解看到 $P$ 的范围,显然可以对节点上放置分部的状态进行状压。因为每个分部收取的...
   题解    0 条评论
省选/NOI-
题意一个有点权和边权的无向图,求 所有点权和为 $0$ 的子图 的最小生成树的权值和。其中点数 $N\le 16$ 。题解看了半天题才得到上面的题意,看到 $N\le 16$ ,显然是状压。用 $f[id]$ 表示当前点集状态为 $id$ 时的最优解,当 $i$ 和 $j$ 状态内的点权和为 $0$ 时,转移方程式很显然:$$f[i|j]=f[i]+\text{Kruskal}(j)$$对每...
   题解    0 条评论
题意有 $N$ 个长度相同的字符串,问恰好与其中 $K$ 个匹配的字符串有多少个。定义满足如下条件的字符串 $x$ 和 $y$ 为匹配的:$len_x=len_y$$\forall 1\le i\le len_x \ , \ x[i]='?' \ or \ x[i]=y[i]$其中 $N\le 15$ ,字符串长度 $len\le 50$ 。题解看数据范围,可以对 $N$ 进行状压。先预处理...
   题解    0 条评论
省选/NOI-
题意学生排队去食堂吃饭,每个学生都有不同的口味 $\text{T}[]$ 。食堂做第 $1$ 到菜不需要时间,之后在口味为 $x$ 的菜后做口味为 $y$ 的菜花费的时间为 $x\oplus y$ 。为了节省总等待时间,食堂有时会不按排队顺序做,但每个同学最多忍受他后面的 $\text{B}[i]$ 个同学在他之前打饭。求等待总时间的最小值。其中人数 $N\le 1000$ ,$\text{...
   题解    0 条评论
省选/NOI-
题意动物园的笼子环形排列,每个小朋友能看到从站的位置开始往后共 $5$ 个笼子的动物,每个小朋友都有喜欢和害怕的动物。可以移走一部分笼子。定义每个小朋友是开心的,当且仅当下列条件之一满足:在视线范围内至少有一个喜欢的动物没被移走。在视线范围内至少有一个害怕的动物被移走。求最优方案,使得开心的小朋友尽可能多。其中动物数 $N\le 10000$ ,小朋友个数 $C\le 50000$ 。题解动...
   题解    0 条评论
省选/NOI-
题意在 $N\times M$ 的图中部署炮兵,只有平原才能部署。每个炮兵的攻击范围为上下左右各延申两格,求方案数。其中 $N\le 100,M\le 10$ 。题解跟 玉米田 差不多,但是因为前两行都对当前状态有影响,所以需要多一维。如果直接开 $\text{f}[105][1024][1024]$ 的数组空间就爆了,所以需要预处理每一行合法的状态。可以发现合法的状态最多 $60$ 种,所...
   题解    0 条评论
提高+/省选-
题意在一个 $N\times M$ 的田地里种草,有的地方不能种,要求不能有两块相邻的。求方案数。其中 $N,M\le 12$ 。题解状压dp。把图存下来,每次枚举时判断状态合不合法即可。$$\text{f}[i][j]+=\text{f}[i-1][k]$$#include<bits/stdc++.h> #define ha 100000000 using namespace...
   题解    0 条评论
提高+/省选-
题意在 $N\times N$ 的棋盘里摆 $k$ 个国王,每个国王可以攻击周围 $8$ 个格子,求国王互不侵犯的摆法有多少种。其中 $N\le 9$ 。题解显然状压dp。可以预处理每一行的合法方案存在 $\text{s}[]$ ,合法方案即没有两个相邻的。用 $\text{f}[i][j][k]$ 表示在第 $i$ 行,合法方案编号为 $j$ ,放了 $k$ 个棋子的方案数。枚举上一行的状...
   题解    2 条评论
提高+/省选-