标签:动态规划-状压DP

题意给出一个 $n(\le 10^5)$ ,求集合 $\{1,2,...,n\}$ 的满足:若 $x$ 在集合中,则 $2x$ 和 $3x$ 不能出现在集合中 的子集个数。题解可以构造一个矩形,横向依次 $\times 3$ ,纵向依次 $\times 2$ ,如下图所示:1 3 9 27 81 243 2 6 18 54 162 486 4 12 36 108 324 972在这个矩形中选...
题解 动态规划-状压DP
省选/NOI-
题意有 $n(\le 18)$ 只绿猪,位置在 $(x_i,y_i)$ 。每次可以从 $(0,0)$ 发射一只小鸟,开口向下的抛物线上的猪会被消灭。问至少要发射多少只小鸟。题解容易想到暴力的状压。用 $f(S)$ 表示消灭集合 $S$ 中的绿猪需要多少只小鸟,预处理出经过 $i,j$ 两只猪的抛物线可以消灭的猪 $s[i][j]$,枚举不在 $S$ 中的两只猪 $i,j$ ,方程式为:$$\...
题解 动态规划 动态规划-状压DP
提高+/省选-
题意给一个数字串 $s(|s|\le 10)$ 和正整数 $d(\le 1000)$ , 统计 $s$ 有多少种不同的排列能被 $d$ 整除(可以有前导 $0$)。题解$|s|$ 较小,考虑状压。用 $f(S,i)$ 表示下标集合 $S$ 内的数都用过了,当前数 $\equiv i\pmod d$ 。每次枚举一个不在 $S$ 的数 $j$ 加入转移,方程式为:$$f(S,i)\rightar...
题解 动态规划 动态规划-状压DP
提高+/省选-
题意给一个 $n(\le 15)$ 个点 $m$ 条边的无向连通图(不存在自环或重边),每条边有一个边权,要求割掉若干条边,使 $1$ 到 $n$ 只有 $1$ 条路径(不经过重复点),问割掉的边权和最小是多少。题解可以发现最后图的形态一定是一条链,链上可能挂了若干个连通块,要最大化图的边权和。$n$ 比较小,考虑状压。用 $f(S,i)$ 表示目前链上的终点为 $i$ ,加入的点集为 $S...
题解 动态规划 动态规划-状压DP
NOI/NOI+/CTSC
题意有 $N$ 张卡片,使用过后会往前跳 $S_i$ 格。有 $M$ 个格子是厄运格,如果跳到就输了,求跳到终点的方案数。$N\le 24 \ , \ M\le 2$ 。题解用 $cnt[i]$ 表示当前走到的格子,很容易想出状压方程:$$f[i]=\begin{cases} 0 \ (cnt[i]\in M) \\ f[i]+f[i \ xor \ 2^{j-1}] \ (cnt[i]\n...
题解 动态规划 动态规划-状压DP
省选/NOI-
题意有 $N$ 个人要排队,要求一队的站在一起,共有 $M$ 队。调整队列的方法为让一部分人出队,再回到不同的空位里。求最少要让多少人出队。$N\le 100000 \ , \ M\le 20$ 。题解对每支队伍是否有序状压,用 $f[i]$ 表示状态为 $i$ 时最少的出队人数。记录第 $j$ 支队伍的人数为 $cnt[j]$ ,设之前排到了第 $l$ 个人,那么现在要排的是 $[l+1,...
题解 动态规划 动态规划-状压DP
提高+/省选-
题意有 $N$ 个人去执行 $N$ 个任务,每个人执行每个任务有不同的成功率,每个人只能执行一个任务,求所有任务都执行的总的成功率。(直接用题面)$N\le 20$ 。题解用 $f[i]$ 表示任务完成状态为 $i$ 时的最大成功率。预处理出 $1$ 的个数 $cnt[i]$ ,枚举任务 $j$ ,很容易得到方程:$$f[i]=\max f[i \ xor \ 2^{j-1} ]+s[cnt...
题解 动态规划 动态规划-状压DP
省选/NOI-
题意用 $K$ 个硬币购买 $N$ 个物品。商店不设找零,可以在购买了连续多个物品后用 一个 硬币支付。求最多能剩下多少钱。$N\le 100000 \ , \ K\le 16$ 。题解看到 $K\le 16$ ,状压。用 $f[i]$ 表示硬币使用状况为 $i$ 时能买前几个物品;预处理出 $v[i][j]$ 表示硬币 $i$ ,从 $j$ 物品开始买,能买到哪个物品;枚举当前用的硬币 $...
题解 动态规划 动态规划-状压DP
提高+/省选-
题意在树上放一些山贼集团的分部,每个分部可以收取根节点到它路径上所有节点的保护费。在节点 $i$ 建立分部 $j$ 花费 $s[i][j]$ 。对于每一个节点,如果它被多个分部收保护费,就可能产生收益或损失。求最优的放置方法,可以得到最大利润。其中点数 $N\le 100$ ,分部个数 $P\le 12$ 。题解看到 $P$ 的范围,显然可以对节点上放置分部的状态进行状压。因为每个分部收取的...
题解 动态规划-树形DP 动态规划-状压DP
省选/NOI-
题意一个有点权和边权的无向图,求 所有点权和为 $0$ 的子图 的最小生成树的权值和。其中点数 $N\le 16$ 。题解看了半天题才得到上面的题意,看到 $N\le 16$ ,显然是状压。用 $f[id]$ 表示当前点集状态为 $id$ 时的最优解,当 $i$ 和 $j$ 状态内的点权和为 $0$ 时,转移方程式很显然:$$f[i|j]=f[i]+\text{Kruskal}(j)$$对每...
题意有 $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$ 进行状压。先预处理...
题解 动态规划-状压DP
省选/NOI-
题意学生排队去食堂吃饭,每个学生都有不同的口味 $\text{T}[]$ 。食堂做第 $1$ 到菜不需要时间,之后在口味为 $x$ 的菜后做口味为 $y$ 的菜花费的时间为 $x\oplus y$ 。为了节省总等待时间,食堂有时会不按排队顺序做,但每个同学最多忍受他后面的 $\text{B}[i]$ 个同学在他之前打饭。求等待总时间的最小值。其中人数 $N\le 1000$ ,$\text{...
题解 动态规划-状压DP
省选/NOI-
题意动物园的笼子环形排列,每个小朋友能看到从站的位置开始往后共 $5$ 个笼子的动物,每个小朋友都有喜欢和害怕的动物。可以移走一部分笼子。定义每个小朋友是开心的,当且仅当下列条件之一满足:在视线范围内至少有一个喜欢的动物没被移走。在视线范围内至少有一个害怕的动物被移走。求最优方案,使得开心的小朋友尽可能多。其中动物数 $N\le 10000$ ,小朋友个数 $C\le 50000$ 。题解动...
题解 动态规划-状压DP
省选/NOI-
题意在 $N\times M$ 的图中部署炮兵,只有平原才能部署。每个炮兵的攻击范围为上下左右各延申两格,求方案数。其中 $N\le 100,M\le 10$ 。题解跟 玉米田 差不多,但是因为前两行都对当前状态有影响,所以需要多一维。如果直接开 $\text{f}[105][1024][1024]$ 的数组空间就爆了,所以需要预处理每一行合法的状态。可以发现合法的状态最多 $60$ 种,所...
题解 动态规划-状压DP
提高+/省选-
题意在一个 $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...
题解 动态规划-状压DP
提高+/省选-
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划50 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP14 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP2 图论4 图论-LCA3 图论-Tarjan9 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束3 图论-强连通分量1 图论-最小环1 图论-最小生成树6 图论-最短/最长路17 图论-树上差分2 图论-桥1 图论-缩点4 图论-负环3 字符串3 字符串-kmp2 思维题3 数学25 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-栈1 数据结构-树状数组3 数据结构-树链剖分10 数据结构-线段树3 数据结构-队列1 比赛-Codeforces18 比赛-JX Round1 比赛-NOIp/CSP4 算法-KM算法1 算法-二分/三分11 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希1 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索20 算法-模拟5 算法-状态压缩4 算法-贪心8 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2