2022年状态压缩的DP之个人整理总结 .pdf

《2022年状态压缩的DP之个人整理总结 .pdf》由会员分享，可在线阅读，更多相关《2022年状态压缩的DP之个人整理总结 .pdf（49页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、状态压缩的DP 第 1 页Auther: 陈江勇2008 年 10月 22 日状态压缩的 DP 方格选数最大hdu2167 . 1 给奶牛安排牛场（pku 2241） . 4 积木块（哈尔滨5085 bircks ） . 7 哈密顿回路(pku 2288) . 11 排列单词使相同位置的字符最多(pku2817 WordStack) . 16 欧拉 pizza 店（ pku3311） . 19 炮兵阵地 (pku 1185) . 22 数 a 的排列有多少个数可以被b 整除（ hust SCU-J Counting numbers ） . 25 最小矩形覆盖（2836 Rectangular

2、Covering ） . 28 4的面板用1*2 的方格覆盖有多少种（pku 3420）. 37 方格选数最大hdu2167 题目大意：Youre given an unlimited number of pebbles to distribute across an N x N game board (N drawn from 3, 15), where each square on the board contains some positive point value between 10 and 99, inclusive. 给你一个N*N 个矩阵，要你选择若干个数，使得最后所选的数总

3、和最大。选数的规则是如果选了某个数，那么它的八个相邻方向的数都不能选。本题用到stringstream 这样处理起来比较方便。状态压缩的DP 。#include #include using namespace std; int f2(115)+10; int num1616,v115,vn,bit20,line; int st,N; char temp1024; void init() int i; memset(bit,0,sizeof(bit); bit0=1; for(i=1;iN;i+) biti=biti-11; void valid() int i,end,j; 名师资料总结 -

4、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 2 页Auther: 陈江勇2008 年 10月 22 日end=1N; bool tag; vn=0; for(i=0;iend;i+) tag=true; for(j=1;jN;j+) if(bitj-1&i) & (bitj&i) tag=false; break; if(tag) for(j=0;j=N) if(fsttfst1s+p) fstt=fst1s+p; /

5、 printf(%d %dn,t,fstt); return; if(s&bitx) dfs(x+2,s,t,p); else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 3 页Auther: 陈江勇2008 年 10月 22 日 if(x=0) if(s&bitx+1)=0) dfs(x+1,s,t,p); dfs(x+2,s,t|bitx,p+numlinex); else dfs(x+3,s,t,

6、p); else if(s&bitx-1)=0)&(s&bitx+1)=0) dfs(x+1,s,t,p); dfs(x+2,s,t|bitx,p+numlinex); else dfs(x+1,s,t,p); /这个漏掉了，一直错，差了好久，分类一定要严密，哎 void out() int i,end=1N; for(i=0;iend;i+) printf(%d ,fsti); printf(n); void DP() memset(f0,0,sizeof(f0); valid(); st=0; / out(); int j; int end=1N; for(line=1;line=N+1;

7、line+) st=1-st; memset(fst,-1,sizeof(fst); for(j=0;jnumiN) N+; gets(temp); i+; if(temp0=0) break; while(true); memset(numN,0,sizeof(numN); init(); DP(); return 0; 给奶牛安排牛场（pku 2241 ）问题描述：N 个 bull， M 个 barn， 每个 bull 都有几个自己喜欢的barn， 要求为每个bull 分配一个 barn，使得每个bull 所分到的barn 都是自己喜欢的，且每个barn 至多只能容纳一个bull 。求合法

8、的分配方案的种数。 （N,M=20 ）解法：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 5 页Auther: 陈江勇2008 年 10月 22 日看到这个问题很容易想到搜索，复杂度O(n!) ，实现很简单，在实际比赛中是一种可行的方法，但是和哈密顿回路问题一样，我们也可以通过状态DP 来解决这个问题。首先我们仍然尝试着分析搜索算法中的冗余问题，如下图：（图 3）和（图 4）分别表示两种搜索的中间状态，（

9、图 3）中红色方框1 表示第 1 头 bull住进了第1 个 barn，然后第 2 头 bull 住进了 barn5，bull3 住进了 barn6，bull4 住进了 barn7，（图 4）中 4 头 bull 所住的 barn 的集合是一样的，但是顺序略有不同。如果还有bull 没有分配barn，那么从 （图 3）和（图 4）开始继续为剩下的bull 分配 barn的方案数肯定是一样的。和哈密顿回路问题类似，用一个二元组 表示前 i 个 bull 分配到用st 表示的 barn 的集合中的所有的方案数，状态转移方程如下：barnst，jstifsumstifj所表示的集合中的一个2, 1(

10、),(求出所有的f() 后，只需要对所有i = n 的 f 求和即可得到方案总数。状态数为 O(n*2n) ，转移复杂度为O(n)，总的时间复杂度是O(n2*2n) 。题目意思很简单，就是要给每个奶牛分配喜欢的球场，问你有多少中分配方法。注意到不大于20，所以对于很容易想到状态压缩的DP. 但是开始的时候由于DP 的顺序不一样，花了两秒多。后来看了别人的程序，也是跟我一样的状态压缩，但是他的时间用了小于1 秒。后来经过自己的分析，发现原来我的DP 的循环顺序跟他的不一样。把自己的代码该过来之后， 200 多毫秒就过了。开始时的程序：Memory: 8284K Time: 2231MS Lang

11、uage: C+ Result: Accepted void DP() 1 2 3 4 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 图 3 图 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 6 页Auther: 陈江勇2008 年 10月 22 日 int i,j,k,t,a; for(i=0;ibitM;i+) f0i=0; f00

12、=1; a=0; for(i=1;i=N;i+) a=1; for(k=0;kbitM;k+) fak=0; for(j=1;j=pi;j+) t=likeij; for(k=0;kbitM;k+) if(fa1k!=0&(k&bitt)=0) fa(k|bitt)+=fa1k; int ans=0; for(k=0;kbitM;k+) ans+=fak; printf(%dn,ans); 仔细分析这个程序，最后一次循环，浪费了判断，比如说在奶牛i 喜欢球场1， 那么状态k在第 0 位必须为 0，但是有bitM / 2个状态这些位都是1 的， （这些状态都是无用的状态，但是这些状态都进行了判断

13、）这样就浪费了很多次判断。改过后的程序： （可以知道该过后的状态转移方程和原来其实是一样的）。void DP() int i,j,k,t,a, b; for(i=0;ibitM;i+) f0i=0; f00=1; a=0; b = 1; for(i=1;i=N;i+) / for(k=0;kbitM;k+) / fbk=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 7 页Auther: 陈江勇200

14、8 年 10月 22 日/ for (k = 0; k bitM; +k) if (fak = 0) continue; for (j = 1; j = pi; +j) t = likeij; if (bitt & k) = 0) fbbitt | k += fak; fak = 0; a = 1 - a; b = 1 - b; int ans=0; for(k=0;kbitM;k+) ans+=fak; printf(%dn,ans); 可以发现，注释掉的那段代码也可以不要。积木块（哈尔滨5085 bircks）Little White bought a new house recently

15、. She doesnt like the design of the floor anyway, so she decides to decorate the floor. Now she has bricks of the 5 shapes below, all with an infinite amount. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 8 页Auther: 陈江勇2008 年 1

16、0月 22 日Bricks cannot overlap each other, and you cannot rotate them to fit in the holes. Now, please tell Little White how many units can she cover using these bricks. InputFor every test case, you are given two integers n and m indicating the floor is an n*m rectangle consisting of n*m 1*1 grids.(1

17、=n=100,1=m=6) Proceed to the end of file. OutputFor every test case, print an integer on a single line, representing the maximum possible area that can be covered. Sample Input1 4 2 3 3 2 4 4 Sample Output0 4 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 49

18、页 - - - - - - - - - 状态压缩的DP 第 9 页Auther: 陈江勇2008 年 10月 22 日12 自己还是太弱了，因为忽略了一种很重要的地方，使得比赛时一直没做出来，直到比赛后才搞定。这道题我是用状态压缩DP 来做，因为每一行最多只有六格，所以选择行来进行状态 DP，且采用三进制数字表示每一行。对于每一行当中的每一格，若为2，则表示它为空且它前一行的该格也为空，若为1，则表示它为空，若为0，则表示它被占据了，举个例子，若一行有5 个格子，那么11210（3 进制数字）表示该行的第1、2、4 个格子为空，第三个格子为空且它前一行的该格也为空，第五个格子被占据。现在要在行

19、与行之间进行状态的转化来计算某行为某个状态时它之前能填充的最大面积。 计算的具体过程如下，有第二行开始枚举放入的木块（当为第二行时只有两种木块可供选择， 在第二行后有五种木块可供选择），其中 from 表示上一行的状态，to 表示本行的状态， 现在以放入题目中的第三种木块为例，因为要放入第三种木块，必须上一行这三个格子都为空且只需上一行这三个格子它们自己为空（不需要它们的上一行该格也为空），这也就是说要上一行三个格子的状态为111 （对应 10 进制就是 13） ，现在放入第三种木块，放入后，上一行三个格子被填满了，当前行对应的三个格子中，只有中间的格子被填充了，所以当前行三个格子的状态是10

20、1 （对应 10 进制就是10） ，又因为放入木块后坐标位置会向后移动 3，当前被填充的面积会增加4，所以当放入第三种木块，要这样写状态转移函数dfs(x+3, from*27+13, to*27+10, n+4);。放入其它的木块同理以及不放入木块同理。现在再说说这个题特别要注意的地方，我比赛时就是忽略了这个地方才一直wa。就是当放入一个木块后，若使得现在要开始放入位置的前一个格子的状态为2（前一格为空且前一格对应的上一行的格子也为空），那么对于木块2、3、5（数字代表第几种木块），不应该还是就这当前位置放入他们，而是还要考虑把他们向左退一格放入，这样才会节省空间，保证最后得到最优解。可以结

21、合下面图片理解我说的意思，即不应该仅向图片1 一样放入3，而是还要考虑向图片2 一样放入3。那么此时转移函数应该这样写if(to%3=2) dfs(x+2, from*9+4, (to-1)*9+1, n+4);。最后再说说怎么记录状态进行状态转移的问题，这点很重要， 因为若没记录好状态，则转移是不成功的，最后也不会得到正确的答案。对于每放入一种木块，from 的改变是固定的，那么to 呢，若 to 也仅仅对应一种的话，那么在一定要处理好行间转换的问题，若to对应所有可能的解，那么对于放入每种木块，要把所有可能的转移函数都得写上。先说说第二种，在第二种的情况下，每次放入木块后，把to 对应的空

22、格子也要分别尝试填充，这样就记录所以可能的状态，使得在求以后行的状态中，可用之前记录的状态来推导，并且计算完每一行后0 就对应了最优解的状态。鉴于第二种情况记录的无效态多且代码量大，这里再说说第一种情况，若对应每个from 只记录一个to 的话，那么在行间转换时，对于每一格，若它上一个的状态为2，则它也为2，若为 1，则它可为2，也可为1，若为 0，则它为1，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 49 页 - - - - - - - - - 状态压缩的DP 第

23、10 页Auther: 陈江勇2008 年 10月 22 日这样写会大大省了代码量，也省去了一些无效状态，但要注意一点就是计算完每一行后，最优解要枚举出该行的所有状态才能算出。对于记录状态转移的第二种做法，对应下面的代码1（81MS） ，对于第一种做法，对应代码2（55MS） 。关于这题网上已经找到了解题报告，不过开始的时候看解题报告一直没有理解，特别是那个(to % 3 = 2) 那边的递归部分。还有关于本题，如果没有看别人的代码，直接写的话，可能是枚举前一行的所有有效状态，然后从每个有效的状态开始DP， （跟在自己以前写的状态DP 很像）不过这样很麻烦， 对于本题其实跟以前的那个1 * 2

24、 的木块其实是类似的， 可以同时 dfs 生成 from 和 to 两个状态这样递推。对于本题，例如：木块3， 为什么只要算前一行的三个方格为空的情况就可以了，而不用枚举所有的8 种状态，当前格为空，同时前格为空或不为空的情况，原因很简单， 那就是前 2 行为空的状态等定不会比只要前一行为空的方格数多，因为要算最后， 所以只要前1 行的为空就可以了。还有关于关于为什么别人写的解题报告里面有to % 3 = 2这个递归，原因很简单，就是因为最后（第5 中）拼图的关系，放了第5 中方格，不能直接就x + 2，对于x + 1 还有空出两个方格，可以放 2， 3， 4 这三种方格， 所以程序中有to

25、% 3 = 2 的递归。但是这样有很多重复的递归，本人通过改进，把第 5 种拼图和第2， 3， 4 种拼图合并来处理，这样就不会有重复的递归了，时间又提高了一点。还有一点值得注意：就是对于不放的情况：少了这个递归就错了：dfs(x+1, from*3+1, to*3+1, n); 请认真想想为什么！ ！#include #include using namespace std; #define MAXN 100 #define MAXC 6 int pwMAXC+1=1; int a22200,rec1017; int p,c; void dfs(int x, int from, int to

26、, int n) if(xc+1) return; if(x=c+1) if(a1-p&1from+n ap&1to) ap&1to=a1-p&1from+n; return; dfs(x+3, from*27+13, to*27+10, n+4);/3 dfs(x+3, from*27+13, to*27+4, n+4);/4 if(p=3) dfs(x+2, from*9+7, to*9+1, n+4);/1 dfs(x+3, from*27+16, to*27+10, n+5);/2 dfs(x+2, from*9+8, to*9+2, n+4);/5 dfs(x + 4, from *

27、 81 + 76, to * 81 + 10, n + 8); /合并 5， 3 dfs(x + 4, from * 81 + 79, to * 81 + 10, n + 9); /合并 5，2 这边是加 9 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 11页Auther: 陈江勇2008 年 10月 22 日dfs(x + 4, from * 81 + 76, to * 81 + 4, n + 8)

28、; /合并5， 4 dfs(x+1, from*3+2, to*3+2, n); dfs(x+1, from*3+1, to*3+2, n); dfs(x+1, from*3+1, to*3+1, n); dfs(x+1, from*3, to*3+1, n); int find_ans() int ans=0; for(int s=0; spwc; s+) if(ans ap&1s) ans=ap&1s; return ans; int main() for(int i=1; i=MAXC; i+) pwi=pwi-1*3; for(c=1; c=MAXC; c+) memset(a,0,s

29、izeof(a); for(p=2; p=MAXN; p+) memset(ap&1,0,sizeof(ap&1); dfs(1,0,0,0); recpc=find_ans(); int n,m; while(scanf(%d%d,&n,&m)!=EOF) printf(%dn,recnm); return 0; 哈密顿回路(pku 2288) 解题报告：这题不难，搞了好久，才搞出来，太粗心了。题目的意思：给你一个无向图，每个节点都有一个值，在没有固定起点和终点的情况下，要你访问每个节点一次（哈密顿路（不是回路） ，使获得的规定值最大。名师资料总结 - - -精品资料欢迎下载 - - - -

30、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 12 页Auther: 陈江勇2008 年 10月 22 日规定的值按以下计算方式，是以下三部分之和。1.所有访问过的节点的vi 之和。2.如果路径为v1,v2, vn,那么还要加上值vv1*vv2+vv2*vv3， 也就加上相邻的两个v的值的积。3.如果路径中相邻的三个节点能构成一个三角形，再加上这相邻的三个v 值的积。Sample Input 2 3 3 2 2 2 1 2 2 3 3 1 4 6 1 2 3

31、 4 1 2 1 3 1 4 2 3 2 4 3 4 Sample Output 22 3 69 1 本题不难，状态压缩的DP. 不过开始的时候没想清楚，一直出错。后来想清楚了，又在程序细节方面出了问题。开始的时候定义的状态：fis 其中 s 是访问节点的状态，相应位为1,表示访问过了。i 为当前访问到的位置。同时用 preis 表示 fis 这个状态的最大值的前一个节点的编号。于是写出了如下的代码。后来知道这样状态都定义错了。因为值的计算方式的第三种的影响，必须保存当前访问的节点，访问节点的状态 （已经访问的节点） ，还有就是所有能到这个状态的前一个节点的编号，而不仅仅值最大的值的前节点的编

32、号，因为后面的节点可能会和前面不是最大的状态的前一节点构成三角形形成更大的值。所以状态应该增加一个。所以就定义状态fijs, i 为当前访问的节点，j 为前一个节点（i 是 j 走的下一个节点） ，s为访问状态的最大值，在j 前面的节点我们就不用记录了，因为和后面状态没有关系。fkit = max (fijs + Value); 状态写对了， DP 的时候方向有错了，循环的顺序又错了，看第二个程序：for ( i = 0; i n; +i) /这样比如f13 第一次有值，但是对于5 1 3 这样的路径状态却没有包含进去。 for (j = 0; j n; +j) 名师资料总结 - - -精品资

33、料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 13 页Auther: 陈江勇2008 年 10月 22 日 if(j = i | !flagij) continue; for (s = biti | bitj; s bitn; +s) for (k = 0; k n; +k) 最后想通了， 看最后一个程序的注释，开始的时候还为这个起点苦恼，开始的时候多了一个start 的循环。s 从 0 ，开始往上推，可以保证正确的解。方向写正确。

34、因为s 递推出来的状态的值t，比s 大，保证了计算顺序不会出问题。#include using namespace std; int g1616; int v14; int n, e; _int64 f13131 13; _int64 num13131 13; int bit14; int sum; void input() scanf(%d%d, &n, &e); int i, a, b; sum = 0; for(i = 0; i n; +i) scanf(%d, &vi); sum += vi; vn = 0; memset(g, 0, sizeof(g); for (i = 0; i

35、e; +i) scanf(%d%d, &a, &b); -a; -b; gab = gba =1; void init() int i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 14 页Auther: 陈江勇2008 年 10月 22 日bit0 = 1; for (i = 1; i 14; +i) biti = biti - 1 1; void DP() int s, i, t, j, k; _

36、int64 ans, tol , tmp; if (n = 1) printf(%d %dn, v0, 1); return; for (i = 0; i n; +i) for (j = 0; j n; +j) memset(fij, 0, bitn*sizeof(_int64); memset(numij, 0, bitn*sizeof(_int64); for (i = 0; i n; +i) for (j = 0; j n; +j) if(!gij) /开始的时候这个忘了continue; s = biti | bitj; fijs =vi + vj + vi * vj; numijs

37、= 1; for (s = 0; s bitn; +s ) for (i = 0; i n; +i) if (s & biti) = 0) continue; for (j = 0; j n; +j) if(j = i | (s & bitj) = 0 | !fijs) /开始这个 !fijs 写到下面一个if 去了。continue; for (k = 0; k n; +k) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 49 页 - - - - - - - - -

38、 状态压缩的DP 第 15 页Auther: 陈江勇2008 年 10月 22 日 if(k = i | k = j | (bitk & s) != 0 | !gki) /开始 !gki 忘了continue; t = s | bitk; tmp = vk * vi + vk; if(gkj != 0) tmp += vi * vj * vk; if (fkit fijs + tmp) fkit = fijs + tmp; numkit = numijs; else if(fkit = fijs + tmp) numkit += numijs; ans = tol = 0; for (i =

39、0; i n; +i) for (j = 0; j n; +j) if(ans fijbitn - 1) ans = fijbitn - 1; tol = numijbitn - 1; else if(ans = fijbitn -1) tol += numijbitn - 1; printf(%I64d %I64dn, ans, tol / 2); int main() init(); int q; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 49 页 - - -

40、 - - - - - - 状态压缩的DP 第 16 页Auther: 陈江勇2008 年 10月 22 日scanf(%d, &q); while(q-) input(); DP(); return 0; 排列单词使相同位置的字符最多(pku2817 WordStack) 题目的意思：给你 N 个字符，要你给给这个N 个单词一个排列，问你最多共有多少个字符和前一行的字符相等（不一定要连续） 。可以在单词的前面加空格。Sample Input 5 abc bcd cde aaa bfcde 0 Sample Output 8 Hint Note: One possible arrangement

41、 yielding this score is: aaa abc bcd cde bfcde Source 算法：这题就是简单的状态DP. 如果第i 个串排在第j 个串后面，那么i 和前一个字符相等的字符的个数一定就是和第j 个串的最多字符相等情况。可以前后移动。（也就是在前面加空格，如果移出左边界，相当于前面前面所有的单词都后移动。为什么是 DP,这个与算哈密顿路径道理是一样的。如果当前用了1, 3, 4， 7 这几个单词，并且第3 个单词，排在最后，那么后面的状态只于第3 个单词有关，而与前三个单词1,4,7 的排列无关。为了避免重复计算用状态压缩的DP。讲到这里，状态压缩的DP 方程应该

42、就不难写了。状态应该包含用了那些单词，最后一个单词是第几个。fji = maxfki - 2k i 为用了那些单词的状态，相应位为1，表示用了该单词，j 以第 j个单词为结尾的情况。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 17 页Auther: 陈江勇2008 年 10月 22 日#include using namespace std; const int maxn = 10; char wor

43、d1012; int commaxnmaxn; int len10; int N; int fmaxn1 maxn, bitmaxn + 1; bool input() scanf(%d, &N); if (N = 0) return false; int i; for (i = 0; i N; +i) scanf(%s, wordi); leni = strlen(wordi); return true; void pre_work() int i, j, k, p, a, b, t, mx; for (i = 0; i N; +i) for (j = i + 1; j N; +j) mx

44、= 0; for (k = 0; k mx ; +k) for (p = 0; p mx; +p) a = k; b = p; t = 0; while(a leni & b mx) mx = t; comij = comji = mx; void init() int i; bit0 = 1; for (i = 1; i = maxn; +i) biti = biti - 1 1; void DP() pre_work(); int i, j, k; for (i = 0; i N; +i) memset(fi, 0, bitN * sizeof(int); for (i = 1; i bi

45、tN; +i) for (j = 0; j N; +j) if (bitj & i) != 0) for (k = 0; k N; +k) if (bitk & i) = 0 & fkbitk | i fji + comjk) fkbitk | i = fji + comjk; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 19 页Auther: 陈江勇2008 年 10月 22 日 int ans =

46、 0; for (i = 0; i ans) ans = fibitN - 1; printf(%dn, ans); int main() init(); while(input() DP(); return 0; 欧拉 pizza 店（ pku3311 ）题目链接： http:/ 题目大意：有一家pizza 店要送pizza 到 n 家。只有一名司机，要求每家都必须送到，最后回到pizza 店。送递过程中可以重复经过任意一家。给出任意两家直接来往所需的时间（来的时间不一定和往的时间相同），求最短的送递时间。Output For each test case, you should outpu

47、t a single number indicating the minimum time to deliver all of the pizzas and return to the pizzeria. Sample Input 3 0 1 10 10 1 0 1 2 10 1 0 10 10 2 10 0 0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 20 页Auther: 陈江勇2008 年

48、10月 22 日此题即状态压缩DP，0 表示pizza 店，其他用1.n 表示。每一家用一位表示其状态（经过与否），经过了就是1，否则为0。那么总的状态数就是2n = 1 n ，maxs = (1 n) - 1 即为最大的状态数。设dpij 表示在状态i 下，当前位置在第j 家的最短时间，方程即为： dpij = mindpi - testjk + akj，k = 1.n，其中testj = 1 (j - 1) ，akj 表示从第 k 家到第j 家的最短时间，DP 前用一次Floyd 求出任意两家之间的最短时间即可。the pizzeria (numbered 0) and the n loc

49、ations (numbers 1 to n). #include using namespace std; const int maxn = 11; int fmaxn1 maxn; int dmaxnmaxn; int bitmaxn + 1; int N; void init() int i; bit0 = 1; for (i = 1; i = maxn; +i) biti = biti - 1 1; bool input() scanf(%d, &N); if (N = 0) return false; int i, j; +N; for (i = 0; i N; +i) for (j

50、 = 0; j N; +j) scanf(%d, &dij); return true; void Floy() int i, j, k; for (k = 0; k N; +k) for (i = 0; i N; +i) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 49 页 - - - - - - - - - 状态压缩的DP 第 21 页Auther: 陈江勇2008 年 10月 22 日 for (j = 0; j N; +j) if (dik + dkj di