记得做过类似于这类题目是能够用组合数学方法来解决的,可惜淡忘了,也找不到了,看了网上的也有人提到过能够用组合公式解决,但是没人做,都是用了状压DP的方法,这个状压非常难讲清楚吧,推荐两篇 第一遍大体看看这个:http://blog.csdn.net/crux_d/article/details/2206736 想要详细实现的时候看看他的解析:http://blog.csdn.net/yan_____/article/details/8719748 #include<iostream> #inc

题意:在一个4*4的方框内摆放了若干个相同的玩具,某人想将这些玩具重新摆放成为他心中理想的状态,规定移动时只能将玩具向上下左右四个方向移动,并且移动的位置不能有玩具,请你用最少的移动次数将初的玩具状态移动到某人心中的目标状态. 题解:状压状态,然后bfs时枚举每一位向四个方向转移即可,记得加vis,表示已经访问过的状态 /************************************************************** Problem: 1054 User: walfy

题目链接 唉,只有AC了这道题才会感叹考场上没有想出解法的我是多么智障. 我甚至连任何想法都没有. 天啊我当时到底在想些什么. AC这道题我就能进前15了诶. 我们发现只要确定了轮廓线那么此时的状态就是唯一的. 那么,用15进制的状态去表示一下此时的轮廓线.详细说来,就是我们有n个数,第i个数表示第i行放了多少棋子,然后我们把这n个数用15进制表示一下(为什么不是m+1进制呢?qwq因为15进制写着方便),就可以爆搜啦 然后因为开O2的关系,map记忆化一下就可以A啦 #include<cstd

题意:有1~n个小环,他们中的有些互相扣在一起,问你至少切开几个能把这写小环串成一条链 思路:还是太菜了,题目给的n<=15,显然可以暴力解决. 用二进制表示每个环切还是不切,然后搜索所有情况.当一种情况满足一下两点:1.切完之后每一串连在一起的环应该是一条链,没有分支没有环:2.当一个环被切开,那么他就可以当做任意串的连接点,那么显然切开的点+1>=串的数量. 代码: #include<set> #include<map> #include<stack>

[题目]1920 空间统计学 [题意]给定m维空间中的n个点坐标,满足每一维坐标大小都在[0,3]之间,现在对于[0,3*m]的每个数字x统计曼哈顿距离为x的有序点对数.\(n \leq 2*10^5,m \leq 9\). [算法]状压DP m范围很小,考虑设计状压DP的状态,可以想到设到达某个坐标j(将m维坐标压成m位四进制数)步数为k(距离等价于步数)的点数,但是难以转移.考虑按维转移,考虑每一维往外走的情况来转移. 设\(f_{i,j,k}\)表示前i维,到达坐标j,步数为k的点数.转移

题目描述 给出一张 $n$ 个点 $m$ 条边的无向图和 $p$ 个特殊点,每个特殊点有一个颜色.要求选出若干条边,使得颜色相同的特殊点在同一个连通块内.输出最小边权和. 输入 第一行包含三个整数 n;m;p,表示情报站的数量,可以建立的通道数量和重要情报站的数 量.接下来 m 行,每行包含三个整数 ui;vi;wi,表示可以建立的通道.最后有 p 行,每行包含 两个整数 ci;di,表示重要情报站的频道和情报站的编号. 输出 输出一行一个整数,表示任意相同频道的情报站之间都建立通道连接所花费的

[NOI2015]寿司晚宴 题目描述 为了庆祝NOI的成功开幕,主办方为大家准备了一场寿司晚宴. 小G和小W作为参加NOI的选手,也被邀请参加了寿司晚宴. 在晚宴上,主办方为大家提供了n−1种不同的寿司,编号1,2,3,⋯,n-1,其中第种寿司的美味度为i+1(即寿司的美味度为从2到n). 现在小G和小W希望每人选一些寿司种类来品尝,他们规定一种品尝方案为不和谐的当且仅当: 小G品尝的寿司种类中存在一种美味度为x的寿司,小W品尝的寿司中存在一种美味度为y的寿司,而x与y不互质. 现在小G和小W希

状压dp的标志 ①数据小 ②通过题目所给出的条件以后得到的特征集合小 一:CF259div2 D: 题目大意:保证b[i]中每个数互质,给出a[i],然后求1~n的abs(a[i]-b[i])最小.a[i]<=30 思路:首先得到b[i]必然小于60.这个很重要,因为我们枚举的b的集合就是60.首先当b如果都取1,那么最大的abs就是30,所以b可以取得的极限是60.然后我们可以得到60里面的所有的素数,这些素数的个数是17.因此我们发现是状压DP. 首先预处理出1~60的包含素数的集合,然后枚

也就作业几题而已,分析一下提醒 最重要的就是,记住,没用的状态无论怎么转移最后都会是没用的状态,所以每次转移以后的有值的状态都是有用的状态. 几种思考方向: 第一种:枚举当前的状态,转移成另外一个状态 第二种:枚举最终状态,然后通过另外一个枚举能转移到这种状态 ①就是给你一个地图,然后这个图上面1的可以放东西,0的不能放,问一共有n个东西,每个东西只能放在特定的几个位置上,最多有几种?POJ2441 这个问题就是,因为地图之间的每个空间都是很大的,如果只是普通的dp是无法进行状态转移的,因此这道

加一个维度,钥匙的状态,状压一下.n很小,钥匙也只有10个,bfs就好了. 忘了数组初始化.以后坚决不犯这种低级错误. #include<cstdio> #include<queue> #include<cstring> using namespace std; +; ]; int k[maxn][maxn]; ,-,,}; ,,,-}; ] = { ,,-,, }; struct node { int x,y,step; int s; node(, ,,) { x =

本题的题眼很明显,N (1 <= N <= 150), M (1 <= M <= 10),摆明了是想让你用状态压缩dp. 整个思路如下:由于要填2*3或者3*2的芯片,那么就要找一个策略来判断到底能不能填. 精华1在此: 找到的策略是,记格子(i,j)的状态有三种: 状态0代表(i,j)和(i-1,j)均可用(可用包括非损坏和未占用) 状态1代表(i,j)可用但(i-1,j)不可用 状态2代表(i,j)和(i-1,j)均不可用. 这样设置状态后,我们可以将填芯片这个问题策略化描述:

Friends Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 668    Accepted Submission(s): 313 Problem Description There are n people and m pairs of friends. For every pair of friends, they can cho

题目链接:https://vijos.org/p/2008 现在回过头去看去年的考试题,发现都不是太难,至少每道题都有头绪了... 这道题的数据范围是18,这么小,直接暴力呗,跑个暴搜就完了,时间也就O(n^3) [思路] 先枚举任意两个的抛物线,这个位置需要O(n^2),接着针对每一个抛物线看可以经过多少点,暴力跑一个,时间复杂度O(n^3),不过这一步可以在枚举抛物线时做.. 接着是用一个数组mark[i][j]记录经过点i,j的抛物线可以穿过哪些点..这个位置,我们就可以用状态压缩解决,一

Solution 数据范围疯狂暗示状压,可是一开始发现状态特别难受. 将每一层的奇偶性状压,预处理所有状态的奇偶性.每一层的输入代表的其实可以是下一层某个点可以被从这一层哪些点转移到. 所以枚举每个状态,再枚举下一层转移到哪个点,统计这个点被这个状态更新的话正边和反边分别的奇偶性,转移即可. 第二层和最后一层单独处理即可. Code #include<bits/stdc++.h> #define mod 998244353 using namespace std; ][( << )

有的DP题,某一部分的状态只有两种,选或不选. 开数组记录,代价太大,转移不方便. 状态压缩意为,用 “0/1“ 表示 “选/不选“ . 把状态表示为二进制整数. There are 10 kinds of people in the world, who knows binary and who doesn't. 用位运算判断条件并转移状态. hdu 6149 Valley Numer II 题目传送门 用f[i][j]表示选到前i个点,状态为j的答案. 枚举其他两个高点. 转移之前判断之前是

http://acm.hdu.edu.cn/showproblem.php?pid=5094 给出n*m矩阵 给出k个障碍,两坐标之间存在墙或门,门最多10种,状压可搞 给出s个钥匙位置及编号,相应的钥匙开相应的门,求从1,1到n,m的最短时间,不能到底则输出-1 这里有一个大坑:有可能同一个位置有多个门或者多个钥匙... 这么坑大丈夫? #include <cstdio> #include <cstdlib> #include <cmath> #include <

问题描述 Bqc经过一段时间的研究发现,要解这种毒需要一种特殊的药物.不幸的是,这种药物在 市面上不存在,没有办法Bqc只好亲自制得这种药物.它含有M种化学物质A1,A2,…,AM.现 在Bqc的手上有N种药材(每种药材只有一种),每种药材含有若干种化学物质(Bqc他有一种 机器,只要将药材放入机器,就能制得相应的药物). Bqc需要你的帮助,他希望你能帮他选取若干种药材,用这些选取的药材制作出Bqc需要 的药物.由于这些化学物质是有毒的,因此你选出来的药物,必须含有这M种化学物质. 有一点需要

树形DP和状压DP和背包DP 树形\(DP\)和状压\(DP\)虽然在\(NOIp\)中考的不多,但是仍然是一个比较常用的算法,因此学好这两个\(DP\)也是很重要的.而背包\(DP\)虽然以前考的次数挺多的,但是现在基本上已经成了人人都能AK的题了,所以也不经常考了. 树形DP 树形DP这个非常特殊,他好像和是唯一一个用深搜实现的DP,所以我们学好它也是应该的,其特点是通过深搜. 思路 先找到一个根节点,然后预处理出所有子树的大小. 然后深搜把最底层的子节点得状态处理出来. 递归回溯到根节点,

吐槽:这道题真心坑...做了一整天,我太蒻了... 题意 构造一棵 $ n $ 个节点的树,要求满足以下条件: 每个非叶子节点至少包含2个儿子: 以节点 $ i $ 为根的子树中必须包含 $ c_i $ 个节点. 给出 $ n (n<=24)$ 和 $ c_i $ ,问是否存在符合条件的树. 分析 看到数据范围,第一时间想到的方法应该是状压DP,用数 $ s $ 表示已经被选入子树的点的集合,将两个以上小的子树合并为大的子树,看最后能否得到 $ s=1<<(n-1)-1 $ 这一集合.这

有的时候,我们会发现一些问题的状态很难直接用几个数表示,这个时候我们就会用到状压dp啦~~. 状压就是状态压缩,就是讲原本复杂难以描述的状态用一个数或者几个数来表示qwq.状态压缩是一个很常用的技巧,把它运用到动态规划中有时候可以方便节省空间和时间,精简状态,方便状态转移. 找状态依然是状压dp的核心qwq. 多数状压dp都是将一个n维,每一维为0或1的状态压缩为一个2n的二进制数,用这个数二进制表示下每一位的值来表示这个状态qwq.(比如说储存一行:011110,每一个数字都表示其对应位置的合