状压

C. 连锁商店 time limit per test 1 second memory limit per test 512 megabytes input standard input output standard output 比特山是一个旅游胜地，它一共有 n个景点，按照海拔高度从低到高依次编号为&...

题目描述 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。 输入格式： 只有一行，包含两个数N，K （ 1 &...

又是一道有合法性检测的状压题。 dp[i][j][k]表示第i行状态为j，i-1行状态为k时前i行放置的最大数量。 注意22行统计二进制数中1的个数时的巧妙方法。 1 #include<cstdio> 2 #include<cstring> 3 #...

1、poj 3254  Corn Fields    状态压缩dp入门题 2、总结：二进制实在巧妙，以前从来没想过可以这样用。 题意：n行m列，1表示肥沃，0表示贫瘠，把牛放在肥沃处，要求所有牛不能相邻，求有多少种放...

题目链接 http://poj.org/problem?id=3254 转自http://blog.csdn.net/harrypoirot/article/details/23163485 #include <stdio.h> #include <math.h> #include <string.h> #include <std...

题目没有起点限制，且每个节点至少访问1次，最多访问2次，所以用三进制数表示节点的状态（选取情况）。 因为三进制数的每一位是0或1或2，所以预处理z状态S的第j位的数是有必要的。 边界条件：dp[tri[i]][i]=0,表...

将车票的使用情况用二进制表示状态，对其进行转移即可。 但是我一开始写的代码是错误的（注释部分），看似思路是正确的，但是暗藏很大的问题。 枚举S，我们要求解的是dp[S][v]，这个是从u转移过来的，不可以写成d...

题面 数据范围 1 ≤ n ≤ 5 × 1 0 5 1\leq n\leq5\times10^5 1≤n≤5×105 。 题解 n ≤ 20 n\leq 20 n≤20 的状压应该都会吧，状态记录已经选了的蛋糕集合，以及蛋糕序列的尾部奶油，然后枚举蛋糕转移。 总共有 10 10...

题面 有一个字符串 s \tt s s 和一个有理数 k \tt k k，可以进行如下操作任意次： 选一个当前串中存在的字符 x \tt x x ，令 i 1 , i 2 , . . . , i m \tt i_1,i_2,...,i_m i1​,i2​,...,im​ 为字符 x \tt x x 存...

参考了I_AM_HelloWord的代码，\(f[i][j]\)表示转态\(i\)时最后一刷为\(j\)的最小代价，上面的块可用暴力填涂，注意边界 #include <cstdio> #include <iostream> #include <cmath> #include &...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1074 题意：给出n个课程，每个课程给出课程名称、截止日期、完成需要的时间，超过截止日期完成的课程每超过一天减少分数1。求最少减...

枚举最后食物 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define R(a,b,c) for(register int a = (b); a <= (c); ++...

状态由\(从前往后排好的长度\)和\(排好的团队\)决定，\(DP\)方程挺有思考价值的。 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath...

题面 有 K K K 个机器人初始分别位于数轴上 x 1 , x 2 , . . . , x K x_1,x_2,...,x_{K} x1​,x2​,...,xK​ 的整点位置。 接下来会经历 N N N 秒，每一秒都会发生如下事件： 每个机器人分别有一半的概率停住不动，...

https://ac.nowcoder.com/acm/contest/1104/B 注意到\(\text{K}\)只有\(12\),因此对起点与每个毕经边对应的点单源最短路，\(\text{DP}\)出最优解 #include <cstring> #include <cstdio> #include <...

将金币状压，然后就没多说的了。 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define R(a,b,c) for(register int a = (b...

题目： 解析： 三进制的状压dp 经过简单的打表发现，在m=5时最多有48种合法状态 然后就向二进制一样枚举当前状态和上一层的状态进行转移就好了 由于第k行是给定的，所以转移时要特判一下第k行，并且注意下一k=1...

题目： p2704 [noi2001]炮兵阵地 解析： 和互不侵犯一样 就是多了一格 用\(f[i][j][k]\)表示第i行，上一行状态为\(j\)，上上行状态为\(k\)的最多的可以放的炮兵 发现\(100\times 1024\times 1024\)开不下 还是通...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1074 题意：给出n个课程，每个课程给出课程名称、截止日期、完成需要的时间，超过截止日期完成的课程每超过一天减少分数1。求最少减...

对于棋盘上每个点，都有几种可能，1.不放  2.横放的前一个  3.横放的后一个  4.竖放的上一个  5.竖放的下一个 由于题目要求每个格子都被填满，所以可能1不存在 然后，我们可以考虑用1表示这个格子被放上了2/3/5这...