poj 2411
设$dp(i, j)$为第$i$行用$j$(状态)的方案总数，注意这里$j$不是编号就是状态！
然后先把行可行的方案标记，然后按行DP要注意，横着的砖是11，竖着的砖是竖着的01，所以($h[i] $或$h[i-1]$)必须全是$1$，不然就会有空隙，然后最重要的是要注意($h[i]$与$h[i-1]$)一定是可行方案，否则会出现“半个砖横向填充”的情况。

对于$1-n$等类似的排列计数问题，以动态规划和组合数学2种大方向为基本解决方向。
我们从小到大插入数字，因此我们现在插的这个数比现在所有在序列里的数都要大。
这样一来就不需要记录是哪些数字插入了(而只要记录插入到了第几个数字)，同时不需要记录每个数字的具体位置，也不需要记录数字的相对位置，而只需记录相对关系的数目(对本题而言就是有几个“<”)
我们设$dp(i, j)$表示前$i$个数字构成的数列中，恰有$j$个”<”号的方案数(“>”号就有$i-j-1$个)
考虑插入数的位置：
1、插入在两个数关系为”<”之间：
显然这样插入会增加一个“>”，那么有$j+1$个位置可以插，那么有状态转移方程$dp(i, j) += dp(i-1, j) * (j+1)$
2、插入在两个数关系为”>”之间：
显然这样插入会增加一个“<”，那么有$(i-j+1)-1$个位置可以插，那么有状态转移方程$dp(i, j) += dp(i-1, j-1) * (i-j)$
综上所述，$dp(i, j) = dp(i-1, j) * (j+1) + dp(i-1, j-1) * (i-j)$

本题的一大瓶颈就是当前钻头能力。所以我们尝试不要存储钻头能力。
钻头能力对之后的状态只会贡献一个数值(就好像初始钻头能力为$w$，实际上你可以按$1$来做，最后再把$ans$乘上$w$)，假设从第$i$个星球开始时钻头能力为$1$，因为正着会有后效性，所以我们设$f(i)$为$[i, n]$的最优数值(即上述$ans$)
很容易就能写出一个状态转移方程(资源型)：
$$f(i) = max(f(i+1), f(i+1) * (1-0.01k) + a[i])$$
维护型类似。
观察方程，发现实际上就是取下$[i+1, n]$的最值而已，所以这题实际上就成了贪心

poj 3311
经典TSP问题，之前做的时候被虐，现在来做就是一道水题。
设$dp(S, i)$为状态$i$最后访问到$j$城市的最优解，那么有状态转移方程
$$dp(S, i) = min(dp(S-i, j), dis(j, i))$$
其中$j$是已经访问过的城市(即在$S$中)，$dis$是两点最短路。
边界是$dp(S, i) = dis(0, i)$，当且仅当即只访问了点$i$
答案是$min(dp(E)(i) + dis(i, 0))$，其中$E$为$n$位$1$的二进制数(即全部访问)
注意图不是对称的，所以$dis(i, j)$是有序的，从$j$到$i$必须是$dis(j, i)$而不是$dis(i, j)$

poj 1185

本题很像这题，唯一不同的是一个物品会影响周围两个方格，那么我们设$dp(i, st(j), st(k))$为第$i$行用状态$k$，第$i-1$行用状态$j$的最优值。那么转移方程即为：
$$dp(i, st(j), st(k)) = max(dp(i, st(t), st(j)) + num(k))$$
其中$t$是与$k$不冲突的所有状态。初始化要初始化$num[i]$(st[i]中的$1$的个数)，我们可以用x&(x-1)来快速消掉$x$最后的$1$，算出$num$。判断是否冲突可以用i&(i<<1), i& (i<<2)来判断，可以视为一个平移的过程，仔细思考可以发现。

模板及讲解

状态压缩动态规划就是用于某种时候DP的状态难以表示时，使用二进制进行存储状态的一种动态规划。通常会用位运算进行操作：

位运算

1、对$x$取反：~x
2、$x+1(x为偶数)$：x|1
3、$2^x$：1<<x
4、$2^{-x}$：1>>x
5、$x的对应值$(例如$0$对$1$，$2$对$3$，$8$对$9$)：x^1
6、构造0~n-1位二进制数全部为1：(1<<n)-1
7、构造形如10,100,100000即[0, k-1]全部为0，[k,k]为1，这样的二进制数：1<<(k-1)

状压DP常用

欲想用状压dp，先在dp方程中加上一维状态S再进行思考有哪些需要知道。

有一些状压 (DP) 可以根据最高位来转移，即低位数+最高位=高位数

1、将a的第k位修改为1：a |= 1<<k;
2、将a的第k位修改为0：a &= ~(1<<k);
3、取第k位：a >> k & 1;
4、判定序列里有没有连续出现的1：a&(a>>1)或a&(a<<1)
5、枚举子集：i = (i - 1) & S
6、取最后一个1：i &= (i - 1)
7、x的二进制表达式中最低位的1所对应的值：lowbit(x) = x & (-x)

三(多)进制状压

Loj 10172

我们相当于把一个整数当做三进制数来看，也就是说$(25)_{10}={221}_3$，我们就维护这个$221$。
我们开一个数组sjc[状态][位]=位上的值 (0, 1, 2)，用来找一个状态每一个位上是什么
这个数组可以用十进制转三进制的方法求得，具体看代码。
然后注意本题要特判$k=1，k=n$，并且只有一行的情况。

异或性质

1、$a \oplus a=0$
2、$a \oplus b \oplus c=a \oplus (b \oplus c)$ (右结合律)
3、$a \oplus 0 = a $

异或题：(核心：按位贪心)
1、两个之间的异或值：Trie树 (最大异或和，CF 888G，十二省联考异或粽子)
2、多个之间的异或值：线性基 (Bzoj 4568)

poj 3254
状态压缩基础题。
题意是有一个矩阵，数为0的地方可以放牛，且牛不可以上下左右相邻，求摆放方案数。
DP解答，我们每行DP，但是这里状态比较复杂，这里要用到状压DP
设$dp(i, st[j])$为第$i$行使用状态$j$的方案数。
状态转移方程：
$$dp(i, st[j]) = \sum dp(i-1, st[k])$$
其中$k$是满足$k$在$i-1$行时与$j$在$i$行时不相邻的状态。
代码中运用了多处位运算技巧。

以后贪心排序多考虑考虑cmp函数的写法….
本题可以把大臣排序(不要排序国王，国王始终在第一位)，然后最后一个大臣的钱就是最多的(显然)
关键是排序的cmp怎么写
我们按照$a[i] * b[i]$排序。证明：对于最后一个大臣，它所得的钱为$W=sum / a / b$，即$W=sum / (a * b)$, 那么使$(a * b)$尽可能大，那么$W$就尽可能小。

严谨证明见算法进阶指南，采用的是临项交换的方法。

(题目数字大，要高精度，但这里没打高精度了。。)

一看题目就想树剖，但是这里是图，怎么办？用最小生成树。我们只需要用最大的那几条边来连接这些点成为一棵树，其他的边是没有用的。求完最大树以后，再树链剖分或者倍增思想，这里没有做倍增只做了树剖，注意树剖的时候边权转点权，边权放到深度深的那个点上，然后处理每一个路径$(u,v)$，对于$LCA(u,v)$是不用加的！刚开始正解和暴力全部写挂这里直接10分。改了之后发现暴力还比正解快500ms。。下面给出树剖代码和暴力代码，以及数据生成器，有用的可以拿去。

这题求最大值最小，显然二分。
我们二分本题的答案，如何处理虫洞的情况？
因为只能改造一个虫洞，那么这个虫洞一定是在某些“不改造虫洞会超过二分答案的路径”上，也就是这些路径的交。
那么我们先把每条路径的时间长求出来，怎么求？树上的路径，用LCA即可，时间复杂度$O(mlogn)$
求出来以后，我们每次二分，都一一检查每个路径的时间，如果大于二分答案，就在树上将这一个路径覆盖，那么问题来了，这里怎么覆盖？直接暴力？$O(mn)$的时间复杂度无法接受。这里方法一是树剖后线段树维护，但是这样的代码量直线上升。我们可以考虑差分序列。在线性的数据结构上的差分序列我们已经很熟悉了，$f[a]+1$, $f[b+1]-1$，那么在树上怎么办？很简单，我们让$f[u]+1, f[v]+1, f[LCA(u, v)]-2$，这样做以后在树上的前缀和$\sum_{k\in son(i)}{f[k]}$就表示该点为到其父亲的这条边被经过的次数，之后再找出所有路径的交，判定一下删除的情况就行了，这个地方边权一定要转化为点权。修改在深度深的那个节点上，否则会出现节点未更新完就判断导致错误，代码中有提示。