此题暴露出了偶对AC自动机的理解还停留在初始阶段，做AC自动机后的图理解不是很清楚，看了以前的AC自动机，打印一些通过AC自动机算法构建的图，总算是明白了一些，dp[i][j]表示敲键盘j次后的当前状态在自动机上面的i状态并且不包含给定串的概率，所以i状态并且i转移到的状态不能是目标串的最后一个字符对应AC自动机上的状态，

#include 

分析：因为物品最多为五个，所以可以申请一个五维数组表示状态，dp[ i ][ j ][ k ][ p ][ s ]表示得到i个物品1，j个物品2，K个物品3，P个物品4， S个物品5所花费最少的钱，于是可以按完全背包进行动态规划往后转移，因为物品可以小于5，所以我另外补充了剩余的物品，补充的物品数量为1，价值为0，数量为0,

然后把每个物品单独卖的时候也看成一个“特殊”的OFFER， 于是背包就是最后答案，WA两次，hash数组开小了..

经典的状态压缩Dp:

分析：因为m<=10，所以可以用状态压缩来表示状态，状态s中二进制为1表示当前位置安置炮兵，可以预先处理“有效”的状态（在不涉及地图的情况下，由攻击范围确定）， 这样可以减少复杂度，然后再从第1行到第n行，枚举可行的状态，再从前面两行中可以达到该行状态来转移，具体见代码：

#include 

分析：做一次多重背包来实现每种面额的最少硬币合成数，注：如果用二进制压缩的话可以不事先对面额从大到小排序，但是如果用一个记录用了当前面额多少的方法来算的话那就得对面额按从大到小进来排序再进行多重背包，网上说可以用单调队列来优化，不过偶还不会...

代码比别人的长了许多啊...代码控制能力还有待提高

#include 

题意：有两个监狱，并且这两个监狱中的人一样多，一个监狱中的一些人和另外一个监狱里的一些人不能在一个监狱里面（一起可能会发生暴乱），现在要调换两个监狱中的人，调换人次数小于等于m/2(m为一个监狱的人数），求最大的调换次数，并且调换后的监狱里面不能有两个在一起会发生暴乱的人。

算法：刚开始看着没思路，看了别人的思路然后加上自己的一些理解，首先如果A监狱里面的第i个人与B监狱里面的第j个人不能在同一直监狱里面，则从i向j连一条无向边，于是最后是一个有多个连通分量的无向图，设每个连通分量在两个监狱

题意：给定两个面额为v1,v2的购物卷，n种商品，每种商号有一个价格和得到它的幸福度，且规定某些物品必须被买，且给定有一件商品可以免费，注意每种商品只能买一次，且两张购物卷不能当成一张使用，也就是如果有价格为11的商品，v1=5, v2=6,那么这样是不能买的，并且规定了某些物品必须买

思路：二维动态规划，另外多加一维表示状态，

dp[ i ][ j ][ 0 ]表示第一张购物卷用了i单位钱，第二张购物卷用了j单位钱，并且没有拿免费物品时能达到的最大幸福度

dp[ i ][ j ][ 1] 表示第一张购物卷用了i单位钱，第

完全背包水题：不多说

#include <iostream>
#include <cstdio>
#include <cstring>
#include 

巨水的01背包：贴着玩玩

#include <iostream>
#include <cstdio>
#include <cstring>
#include 

此题写得之杯具：题意不难理解，状态方程也不难推出，但是WA无数次才AC，主要原因是因为我把

long long的输出写成了printf("%lld\n", ret); 去了，杯具啊，改成%I64d就AC了，吐血。还是语言的基础功底薄弱造成的，

不说了，贴个代码，龟速代码...

#include <iostream>

过的人不知道为啥不是很多，思路挺简单， 主要就是这题背包容量是物品的件数，然后就可以用一个数组记录即可，

题意：给定n个物品，每个物品有一个价值，求第一个不能用这n个物品组成的数，其它的比较好理解。

写得比较简单，马上有事出去了，就到这吧，回来再写写..

#include <iostream>

非常好的多重背包，把偶的模板测试出来在这种记录路径上面是不可行的，菜啊，

题意：给定一个面值Price, 1美分的硬币有c[1]个, 5美分的硬币有c[2]个，10美分的硬币有c[3]个，25美分的硬币有c[4]个，求用给定的硬币兑换Price面额的钱，并且要求硬币数最多，求出每种硬币得用多少个.

如果用二进制压缩的话用超时，听说以前不会超时，应该是数据加强了，然后我用了一种记录了用了多少个的方法来进行背包，不停的WAWA，，，后来改了一下才过掉了，看来得更新模板了，

提供几种数据：

6867 2136 1040 0 0

比较水的状态压缩题，需要注意的是相邻之间的square不能同时为1,也就是不能同时都种植，别忘了检查上下边

#include