发现自己好久好久没有写点东西了。呵呵！……

今天做了下hdu3475http://acm.hdu.edu.cn/showproblem.php?pid=3475，自己用了一种比较诡异的方法，没想法跑到了第一，以62ms的速度领先于第二名（281ms）。于是再这里和大家分享一下。

题目大意：

有一个n*m（1<=n<=100, 1<=m<=10）的矩阵，每一个格子有一盏灯，对于每一盏灯，要不就是开着要不就是关着，现在要你把所有的灯都关掉，每一次操作可以改变每一盏灯的状态（关到开，开到关），问最少要操作几次。对于每一盏灯和他相邻的8盏灯都有可能存在连线。当你改变一盏灯的状态的时候，和他有直接相连的灯都会改变状态。

题目分析：

当然这个题目可以同解方程的方法去做，但是好像时间复杂度过不去，我数学是个菜鸟，不好说多少。

还是讲讲我的方法吧。从题目的数据范围上看，m最多只有10，那就是状态压缩dp了，用2^m个状态表示某一行的灯的状态。但是由于改变某一行中一个灯的状态，可能影响它上一行等的状态，也可能影响下一行的状态，这样，我们至少要记录两行的状态才能进行转移。于是，我们定义数组dp[i=100][state1=1024][state2=1024]，来表示第i行以后，第i行的状态为state1，第i+1行的状态为state2，第1至i-1行的状态均为0（所有的灯都关着）的最少操作数。计算一下会发现这样的dp数组肯定是会内存的，所以是要用滚动数组的。

状态转移的时候，用2^m枚举第i+1行的那些灯是进行过操作的（很显然一个灯是不会进行一次以上的操作的），然后进行转移，转移时一定要注意，对第i+1行操作后，第i行灯的状态一定要是全部关掉的。这里完全可以先枚举第i+1行的状态，在根据第i+1行对第i行灯的影响，去确定第i行灯的状态。这样总的空间复杂度为O(2*2^20)，时间复杂度为(100*2^10*2^10)，可以看到，空间能过得去，但是时间复杂度貌似还是有点勉强的，已经到了10^8。

其实有很多状态都是不可能的，能不能在转移的时候不出现这些状态？于是有了诡异的想法，就是把状态数组的最后一维改成链表，这样，枚举完第i+1行的操作状态后，直接对第i行能全部变成0的状态进行转移，这些都是合法的状态。其实这样做的理论复杂度还比原先方法还高，应为在链表中插入一个元素的时候是要遍历整个链表的，但由于链表元素比较少，真实的效果还是很好的。

这种方法再用于dp数组中合法状态很稀疏的情况还是比较好的，其他情况最会更慢。