作者存档：edward_mj

[POJ 2663]状态压缩动态规划

【题目大意】给定一个3*N的block，然后要你求用2*1或1*2的格子填满它有多少种方案。

【算法分析】F[I,J]表示第i行，状态为j的时候的方案数。而对于j，1表示需要向下延伸，0表示不需要向下延伸。

【其它】1A，很久没做状态压缩，有点手生了。。。

6418536 edward2 2663 Accepted 168K 0MS C++ 828B 2010-02-06 20:10:21

【CODE】

#include

HDU月赛

今天被虐了5个小时。一整天就做了两道题。果然，ACM和OI差别还是非常大的。。。

一开始看到前两题，数学，直接放弃。然后看到第3题，感觉很简单，因为之前做过一个类似的，而且比这个还要难，算是加强版，所以1A秒杀。然后切出去看problem list。发现最后一题最多人AC，就去做最后一题。做了才发现代码量非常大，接近两百行，如果有模板，应该是水得。。。不过很可惜，我不是职业acmer，没有模板，所以。。。敲了N久，调试了大概1.5个小时，1A！

然后回看第2题，用等比数列求和公式把数列的通项先推出来，然后发现实际上是求x^n mod a0=1所对应的最小的n值，然后与肥闽讨论了N久，决定暴力。然后TLE，MLE。。。换了3种hash，全部挂掉了。。。于是，再次果断放弃。

然后最后看到第4题也比较多人A，然后就去做，写了个200+行的A*，还没调出样例，比赛结束了= =

虽然比较悲剧，但是也居然排到了13名。。。

最后发现一点，数学差得太远了，差得更远的是英语。。。

另外，YM DIY群的AC大牛和UranusX大牛。。。就是第一和第四那两只。。

Rank Team Solved Penalty 1001 1002 1003 1004 1005 1006 1007 1008 1009 1 AC&&ZT&&LCC 5 11:22:00 02:27:04
(-2) 01:43:33
(-3) 01:34:23 02:46:20 (-20) 01:10:40 2 yaya&zgmf_x20a&Arios 5 18:26:30 01:15:05 02:32:55
(-1) 03:30:25
(-4) 04:50:37
(-1) 03:57:28
(-1) 3 万物皆数 4 12:58:12 02:03:22 02:27:23
(-4) 04:12:18 02:55:09 4 UranusX 4 13:21:39 03:15:44
(-4) 00:57:45
(-1) 04:42:43 01:45:27
(-3) 5 whu_高云翔 4 13:30:39 03:06:27
(-2) 04:04:39
(-2) (-3) 03:08:40
(-1) 01:30:53 6 囧の軌跡 3 07:22:08 03:20:25
(-1) 01:33:08 02:08:35 7 z__jj 3 07:35:38 (-1) 04:35:08
(-2) 00:57:31 (-9) 01:22:59 8 majiaNO.1 3 08:50:19 03:28:09
(-4) 01:29:53 (-5) 02:12:17
(-1) 9 zsasuke 3 10:58:14 01:02:45
(-5) 04:25:05
(-2) (-2) 02:30:24
(-2) 10 ggcc11 3 10:59:01 03:19:09
(-3) 02:37:14 04:02:38 11 NewHorizon 3 11:41:02 03:04:23 04:05:31 (-1) 04:31:08 12 gtzygtzy 3 12:15:16 04:32:14
(-1) 03:41:52 03:41:10 13 cwj 2 03:31:25 (-5) 01:14:43 02:16:42 14 wccn 2 04:40:00 01:20:16
(-1) (-3) 01:59:44
(-3) 15 SHNU_FireStar 2 04:53:01 (-1) 02:09:08
(-1) (-1) 02:23:53 16 喔拉拉 2 05:08:49 (-11) 01:17:14
(-2) 03:11:35 17 依然紫轩 2 05:13:37 01:35:25 03:38:12 (-3) 18 seabao 2 05:29:00 03:35:46 01:33:14
(-1) 19 visitor00 2 05:31:44 (-8) 02:07:52 03:03:52
(-1) 20 Rexer 2 05:38:03 04:33:54 (-2) 00:44:09
(-1) 21 starvae 2 05:42:57 04:06:38 (-1) 01:36:19 22 WHU_123 2 06:16:57 02:03:51
(-1) 03:33:06
(-1) 23 foreverlin 2 06:47:24 (-7) 03:18:22
(-1) (-3) 02:49:02
(-1) 24 majia 2 07:02:44 03:38:15
(-2) (-4) 02:44:29 25 山寨队 2 07:30:31 (-2) 03:52:24 02:58:07
(-2) 26 ReDow 2 07:59:30 (-5) 03:03:34
(-1) (-5) 03:55:56
(-2) 27 kaka8 2 08:05:20 (-3) 04:49:39
(-1) 02:55:41 28 xxjx 2 08:34:33 03:03:48
(-2) (-4) (-1) 04:30:45
(-1) 29 UESTC-Arbiter 2 09:36:12 (-6) 04:02:13
(-3) 02:33:59
(-6) 30 yrjie 2 12:01:28 (-5) 04:52:28
(-12) 02:29:00
(-2) 31 rectaflex 2 12:23:55 (-2) 04:04:43
(-15) 02:19:12
(-3) 32 RaceBug 1 01:08:35 (-5) 01:08:35 33 luther 1 01:39:32 (-5) 01:19:32
(-1) 34 autumncat 1 01:49:49 (-3) 01:09:49
(-2) 35 PlayerII 1 02:08:41 02:08:41 (-4) 36 whu_fatboy 1 02:09:08 (-2) (-5) 02:09:08 37 zjshark 1 02:23:00 02:23:00 38 PrimeMusic 1 02:29:17 (-3) 02:29:17 39 tao 1 02:46:12 (-2) 02:06:12
(-2) 40 open 1 02:57:15 02:37:15
(-1) 41 qu317058542 1 03:13:38 01:33:38
(-5) 42 UESTC_09P27 1 03:26:50 03:06:50
(-1) 43 chenlie 1 03:28:35 (-1) 03:28:35 44 Jsky 1 03:31:10 03:31:10 45 kimhmguen 1 03:32:12 03:32:12 46 surffor 1 03:41:03 (-2) 03:41:03 47 弯弯陈 1 03:44:44 03:24:44
(-1) 48 cowmick 1 03:46:18 (-1) 03:06:18
(-2) 49 yudaer 1 03:55:46 (-9) 03:35:46
(-1) 50 skddj 1 04:03:49 03:43:49
(-1)

二分图匹配总结

对于任意图：

|最小边覆盖|+|最大匹配|=|V|

二分图的最大匹配=最小点覆盖数

对于二分图：

以下数值等价.

最大匹配

最小点覆盖

|V|-最大独立集(二分图or有向无环图)

|V|-最小边覆盖数

|V|-最小路径覆盖数(有向无环图)

|V|-最小路径覆盖数/2(无向图)

（上面括号里有有向无环图的，均是将一个点拆成两个点连边匹配）

由于任意图的那几个几乎用不到于是这里只贴二分图的定义

最小点覆盖：理解为点覆盖边，即用最小的点覆盖所有的边。(若一条边的其中一个端点被选用，这条边就被覆盖了)

最大独立集：求一个最大的点集，里面的点不存在任何的边相连。

最小边覆盖：理解为边覆盖点，用最少的边把图中的点全部覆盖。

最小路径覆盖：用最少的路径把图中的所有点覆盖。

另外：最大独立集与最小覆盖集互补。

推广到有权的形式也一样,即最大点权独立集与最小点权覆盖集互补

求最小点权覆盖集可以这样求：

先对图黑白染色，然后向白色的点放X部，黑色的点放Y部。

1、连边[S,i],容量等于i的点权。（对于二分图的X集）

2、连边[i,T],容量等于i的点权。（对于二分图的Y集）

3、对于有边的i和j连边[i,j]（i∈X，j∈Y）,容量为INF

最后得出的最大流就是最小点权覆盖，实际上是最小割与之对应。

对于求了传递闭包以后的有向无环图：

最大反链=|V|-最大匹配