我的第一道状态空间DP题的详细解题报告

清疚 2022-01-12 08:05 159阅读 0赞

POJ 2817 WordStack 解题报告

题目链接：[http://acm.pku.edu.cn/JudgeOnline/problem?id=2817][http_acm.pku.edu.cn_JudgeOnline_problem_id_2817]

题目主要用到的算法：状态空间dp

题目描述：  
这个题的意思是第一行给出case数N (1 <= N <= 10)，然后给出N个单词，每个一行，当输入不是正整数的时候结束。每个单词最多10个字母。  
Sample Input  
5  
abc  
bcd  
cde  
aaa  
bfcde  
0  
要求的是，按任意顺序排列这些单词，可以在单词前面加任意个空格，使得相邻的单词上下对应的字母数目最多，并输出最多是多少。  
Sample Output  
8  
比如sample里面的8，是这样得来的：  
aaa  
abc  
bcd  
cde  
bfcde  
注意只有相邻单词的字母上下对应才算对应。

我AC的代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] AC的代码   
 1![None.gif][]  
 2![None.gif][]\#include <cstdio>  
 3![None.gif][]\#include <cmath>  
 4![None.gif][]\#include <cstring>  
 5![None.gif][]  
 6![None.gif][]char word\[11\]\[15\];  
 7![None.gif][]int mm\[11\]\[11\];  
 8![None.gif][]int len\[11\];  
 9![None.gif][]int n;  
10![None.gif][]int dp\[2000\]\[11\];  
11![None.gif][]  
12![None.gif][]void Cal( int a, int b ) //word\[a\]和word\[b\]有多少公共字母，存在mm\[a\]\[b\]里,test OK  
13![ExpandedBlockStart.gif][]![ContractedBlock.gif][]![dot.gif][]\{  
14![InBlock.gif][]int max =0;  
15![InBlock.gif][]for ( int i =0; i < len\[a\]; \++i )  
16![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
17![InBlock.gif][]int result =0;  
18![InBlock.gif][]for ( int j =0; j < len\[b\]; \++j )  
19![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
20![InBlock.gif][]if ( i\+j<len\[a\] && word\[a\]\[i\+j\] == word\[b\]\[j\] ) \++result;  
21![ExpandedSubBlockEnd.gif][] \}  
22![InBlock.gif][] max >?= result;  
23![ExpandedSubBlockEnd.gif][] \}  
24![InBlock.gif][]for ( int i =1; i < len\[b\]; \++i )  
25![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
26![InBlock.gif][]int result =0;  
27![InBlock.gif][]for ( int j =0; j < len\[a\]; \++j )  
28![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
29![InBlock.gif][]if ( i\+j<len\[b\] && word\[b\]\[i\+j\] == word\[a\]\[j\] ) \++result;  
30![ExpandedSubBlockEnd.gif][] \}  
31![InBlock.gif][] max >?= result;  
32![ExpandedSubBlockEnd.gif][] \}  
33![InBlock.gif][] mm\[a\]\[b\] = mm\[b\]\[a\] = max;  
34![ExpandedBlockEnd.gif][]\}  
35![None.gif][]  
36![None.gif][]int Fun( int state, int last )  
37![ExpandedBlockStart.gif][]![ContractedBlock.gif][]![dot.gif][]\{  
38![InBlock.gif][]int max =0;  
39![InBlock.gif][]int state\_t = state;  
40![InBlock.gif][] state\_t &= (~(1<<(last\-1)));  
41![InBlock.gif][]if ( state\_t ==0 ) return0;  
42![InBlock.gif][]if ( dp\[state\]\[last\] ) return dp\[state\]\[last\];  
43![InBlock.gif][]  
44![InBlock.gif][]for ( int i =0 ; i < n; \++i )  
45![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
46![InBlock.gif][]int result =0;  
47![InBlock.gif][]int tmp = state\_t&(~(1<<i));  
48![InBlock.gif][]if ( tmp != state\_t ) result = Fun( state\_t, i\+1 )\+mm\[i\+1\]\[last\];  
49![InBlock.gif][] max >?= result;  
50![ExpandedSubBlockEnd.gif][] \}  
51![InBlock.gif][]  
52![InBlock.gif][] dp\[state\]\[last\] = max;  
53![InBlock.gif][]return max;  
54![ExpandedBlockEnd.gif][]\}  
55![None.gif][]  
56![None.gif][]int main()  
57![ExpandedBlockStart.gif][]![ContractedBlock.gif][]![dot.gif][]\{  
58![InBlock.gif][]while ( scanf( "%d", &n ), n>0 )  
59![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
60![InBlock.gif][]int max =0;  
61![InBlock.gif][]int power = (int)pow( 2, n );  
62![InBlock.gif][]  
63![InBlock.gif][]for ( int i =0; i < power; \++i )  
64![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
65![InBlock.gif][]for ( int j =0; j <= n; \++j )  
66![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
67![InBlock.gif][] dp\[i\]\[j\] =0;  
68![ExpandedSubBlockEnd.gif][] \}  
69![ExpandedSubBlockEnd.gif][] \}  
70![InBlock.gif][]  
71![InBlock.gif][]for ( int i =1; i <= n; \++i )  
72![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
73![InBlock.gif][] scanf( "%s", word\[i\] );  
74![InBlock.gif][] len\[i\] = strlen( word\[i\] );  
75![ExpandedSubBlockEnd.gif][] \}  
76![InBlock.gif][]  
77![InBlock.gif][]for ( int i =1; i <= n; \++i )  
78![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
79![InBlock.gif][]for ( int j = i\+1; j <= n; \++j )  
80![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
81![InBlock.gif][] Cal( i, j ); //Cal函数算word两两之间的最大公共字母数存到mm里   
82![ExpandedSubBlockEnd.gif][] \}  
83![ExpandedSubBlockEnd.gif][] \}  
84![InBlock.gif][]  
85![InBlock.gif][]for ( int i =1; i <= n; \++i )  
86![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
87![InBlock.gif][]int tt = Fun( power\-1, i );//Fun函数用来求dp\[\]\[\]的值，也就是全部单词都放满，最后一行是i的情况下总的最大公共字母数   
88![InBlock.gif][] max >?= tt;  
89![ExpandedSubBlockEnd.gif][] \}  
90![InBlock.gif][] printf( "%d\\n", max );  
91![ExpandedSubBlockEnd.gif][] \}  
92![InBlock.gif][]return0;  
93![ExpandedBlockEnd.gif][]\}

思路：分析这个题目，我们应该很容易就看出，结果只与单词的排列顺序有关，至于在每个单词前面加几个空格对结果是不影响的。所以我们可以首先统计这n个单词两两之间最多能有多少个对应的字母，放到数组mm\[11\]\[11\]中(因为题目说n最大是10)。数组名取得不太好哈:-P.比如sample里面的五个单词计算出的mm数组应该是这样的  
0 0 0 0 0 0  
0 0 2 1 1 1  
0 2 0 2 0 2  
0 1 2 0 0 3  
0 1 0 0 0 0  
0 1 2 3 0 0  
mm\[i\]\[j\] 是 word\[i\]和word\[j\]前面加任意个空格能对应的最多字母数。我的代码里是用一个Cal函数实现的这个功能。其中mm数组是全局变量。

1 ![None.gif][] void  Cal(  int  a,  int  b )  // word\[a\]和word\[b\]有多少公共字母，存在mm\[a\]\[b\]里,test OK   
  2 ![ExpandedBlockStart.gif][]![ContractedBlock.gif][] ![dot.gif][] \{  
 3![InBlock.gif][]int max =0;  
 4![InBlock.gif][]//以word\[a\]作为基准，依次在word\[b\]前面添加1～len\[a\]-1这么多空格，看最多能有多少个字母匹配  
 5![InBlock.gif][]for ( int i =0; i < len\[a\]; \++i )  
 6![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
 7![InBlock.gif][]int result =0;  
 8![InBlock.gif][]for ( int j =0; j < len\[b\]; \++j )  
 9![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
10![InBlock.gif][]if ( i\+j<len\[a\] && word\[a\]\[i\+j\] == word\[b\]\[j\] ) \++result;  
11![ExpandedSubBlockEnd.gif][] \}  
12![InBlock.gif][] max >?= result;//">?="这个操作符的意思是二者中取最大的赋给max，可能在vc6.0里不支持  
13![ExpandedSubBlockEnd.gif][] \}  
14![InBlock.gif][]//和上面的代码类似，word\[b\]不动，在word\[a\]前面添加空格。  
15![InBlock.gif][]for ( int i =1; i < len\[b\]; \++i )  
16![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
17![InBlock.gif][]int result =0;  
18![InBlock.gif][]for ( int j =0; j < len\[a\]; \++j )  
19![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
20![InBlock.gif][]if ( i\+j<len\[b\] && word\[b\]\[i\+j\] == word\[a\]\[j\] ) \++result;  
21![ExpandedSubBlockEnd.gif][] \}  
22![InBlock.gif][] max >?= result;  
23![ExpandedSubBlockEnd.gif][] \}  
24![InBlock.gif][] mm\[a\]\[b\] = mm\[b\]\[a\] = max;//这个矩阵是对称的  
25![ExpandedBlockEnd.gif][]\}

对这个题目，不知大家是不是想到了全排列的方法呢？就是把这n个单词全部的可能放置的顺序都排列出来，把上下相邻的公共字母数相加，哪种排列得到的结果最大，就是最终结果。  
首先肯定这个做法是绝对正确的，而且也可以用这个做法AC这个题目（见附代码）。但是，这个做法效率比较低，用了600ms多才跑完数据。而且这种做法没有学到我们要学习的内容，状态空间dp。

接下来给出的是最关键的部分，状态空间dp部分的代码，只有短短的14行，用心理解便不困难

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] Fun函数   
 1![None.gif][]int dp\[2000\]\[11\];//其实2^10=1024就够用了，不需要2000这么多，呵呵  
 2![None.gif][]int Fun( int state, int last )  
 3![ExpandedBlockStart.gif][]![ContractedBlock.gif][]![dot.gif][]\{  
 4![InBlock.gif][]int max =0;  
 5![InBlock.gif][]int state\_t = state;  
 6![InBlock.gif][] state\_t &= (~(1<<(last\-1)));  
 7![InBlock.gif][]if ( state\_t ==0 ) return0;  
 8![InBlock.gif][]if ( dp\[state\]\[last\] ) return dp\[state\]\[last\];  
 9![InBlock.gif][]for ( int i =0 ; i < n; \++i )  
10![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
11![InBlock.gif][]if ( state\_t&(~(1<<i)) != state\_t ) max >?= Fun( state\_t, i\+1 )\+mm\[i\+1\]\[last\];  
12![ExpandedSubBlockEnd.gif][] \}  
13![InBlock.gif][] dp\[state\]\[last\] = max;  
14![InBlock.gif][]return max;  
15![ExpandedBlockEnd.gif][]\}

我先来解释思路再解释这段代码。  
其中主函数对Fun函数的调用部分代码如下：

1  int  max  =  0 ;  
 2  int  power  =  ( int )pow(  2 , n );  
 3   
 4  for  (  int  i  =  1 ; i  <=  n;  \++ i )  
 5  \{  
 6  int  tt  =  Fun( power \- 1 , i ); // Fun函数用来求dp\[\]\[\]的值，也就是全部单词都放满，最后一行是i的情况下总的最大公共字母数    
 7  max  >?=  tt;  
 8  \}  
 9  printf(  " %d\\n " , max );

int Fun( int state, int last )函数的作用如注释所说，Fun函数的第一个参数state表示单词填入的状态，在这里，power-1表示的是所有的单词都已经放到排列里面的状态（我在后面会解释为什么）。第二个参数last表示最后添入的单词是哪个。这段代码的意思是：全部单词都填入，且最后填入的单词是word\[i\]的时候，总的最多的公共字母数是多少，当i取遍1～n的时候，就包括了全部的情况。取最大，就是我们要的结果。比如sample中，power-1 = 31（31的二进制码是11111）假设i=3，Fun(31,3)就表示下面的情况  
word\[x\]  
word\[y\]  
word\[z\]  
word\[a\]  
word\[3\]  
也就是说，x y z a是1 2 4 5的任意排列，或者说全部排列，然后最后一行必须是word\[i\],也就是word\[3\],取总公共字母数最多的值作为Fun函数的返回值。

现在我们回头看Fun函数是如何实现的。

1   
  2 int  Fun(  int  state,  int  last )  // 第一个参数state表示状态，也就是各个单词的取用情况，是用二进制的位运算解决的。因为每个单词只有两种状态，被用了和没被用，那我们就用1表示取了这个单词，0表示没取。每一位表示一个单词的取用情况,第i位表示第i-1个单词是否被取。比如10011表示word\[5\]word\[2\]word\[1\]被取，而word\[4\]word\[3\]未被取。   
  3 \{  
  4  int  max  =  0 ;  
  5  int  state\_t  =  (state  &  ( ~ ( 1 << (last \- 1 )));  // state\_t是state去掉last的状态。   
  6  if  ( state\_t  ==  0  )  return  0 ;  // 如果state去掉last以后是0，也就是说，前面一个单词都没取，那last就是第一个单词，没有和它相邻的单词，返回0   
  7  if  ( dp\[state\]\[last\] )  return  dp\[state\]\[last\];  // 记忆化搜索   
  8   
  9  for  (  int  i  =  0  ; i  <  n;  \++ i )  // 让n个单词都和last相邻一次，取最大值   
 10  \{  
 11  if  ( state\_t & ( ~ ( 1 << i))  !=  state\_t ) max  >?=  Fun( state\_t, i \+ 1  ) \+ mm\[i \+ 1 \]\[last\]; // 如果state\_t的i这位是1，也就是说，state\_t包括word\[i+1\],那么递归调用Fun函数得到state\_t包括的所有单词都作为末一行的最大公共字母数，此时word\[i+1\]作为word\[last\]的相邻行，所以再加上mm\[i+1\]\[last\]，取最大值存起来就可以了   
 12  \}  
 13   
 14  dp\[state\]\[last\]  =  max;  
 15  return  max;  
 16 \}

我觉得状态dp首先是个搜索，然后加上dp提高效率。顾名思义这个dp保存的是这种状态的最优结果。这是我的第一道状态dp题，这类题也仅仅做过两道而已，有什么不对和可以优化的地方请大侠们批评指正。

附：全排列的慢速代码

1 ![None.gif][] // 枚举水过去的代码    
  2 ![None.gif][] \#include  < iostream >   
  3 ![None.gif][]\#include  < vector >   
  4 ![None.gif][]\#include  < algorithm >   
  5 ![None.gif][] using  std::vector;  
  6 ![None.gif][] using  std:: string ;  
  7 ![None.gif][]  
  8 ![ExpandedBlockStart.gif][]![ContractedBlock.gif][] int  dp\[ 10 \]\[ 10 \]  =  ![dot.gif][] \{ 0\} ;  
  9 ![None.gif][]  
 10 ![None.gif][] void  F(  string  a,  string  b,  int  aa,  int  bb )  
 11 ![ExpandedBlockStart.gif][]![ContractedBlock.gif][] ![dot.gif][] \{  
12![InBlock.gif][]int max =0;  
13![InBlock.gif][]string tmp;  
14![InBlock.gif][]for ( int i =0; i != a.size(); \++i )  
15![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
16![InBlock.gif][]int result =0;  
17![InBlock.gif][]for ( int j =0; j != b.size() ; \++j )  
18![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
19![InBlock.gif][]if ( i\+j < a.size() && b\[j\] == a\[i\+j\] ) \++result;  
20![ExpandedSubBlockEnd.gif][] \}  
21![InBlock.gif][]if ( result > max ) max = result;  
22![ExpandedSubBlockEnd.gif][] \}  
23![InBlock.gif][] tmp = a;  
24![InBlock.gif][] a = b;  
25![InBlock.gif][] b = tmp;  
26![InBlock.gif][]for ( int i =0; i != a.size(); \++i )  
27![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
28![InBlock.gif][]int result =0;  
29![InBlock.gif][]for ( int j =0; j != b.size(); \++j )  
30![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
31![InBlock.gif][]if ( i\+j < a.size() && b\[j\] == a\[i\+j\] ) \++result;  
32![ExpandedSubBlockEnd.gif][] \}  
33![InBlock.gif][]if ( result > max ) max = result;  
34![ExpandedSubBlockEnd.gif][] \}  
35![InBlock.gif][] dp\[aa\]\[bb\] = dp\[bb\]\[aa\] = max;  
36![ExpandedBlockEnd.gif][]\}   
 37 ![None.gif][]  
 38 ![None.gif][] vector < string >  word;  
 39 ![None.gif][] vector < int >  id;  
 40 ![None.gif][]  
 41 ![None.gif][] int  main()  
 42 ![ExpandedBlockStart.gif][]![ContractedBlock.gif][] ![dot.gif][] \{  
43![InBlock.gif][]int n;  
44![InBlock.gif][]while ( scanf( "%d", &n )!=EOF && n >0 )  
45![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
46![InBlock.gif][]int max =0;  
47![InBlock.gif][]int result =0;  
48![InBlock.gif][]for ( int i =0; i < n; \++i )  
49![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
50![InBlock.gif][]string tmp;  
51![InBlock.gif][] std::cin>>tmp;  
52![InBlock.gif][] word.push\_back(tmp);  
53![InBlock.gif][] id.push\_back( i );  
54![ExpandedSubBlockEnd.gif][] \}  
55![InBlock.gif][] sort( word.begin(), word.end() );  
56![InBlock.gif][]  
57![InBlock.gif][]for ( int i =0; i < n; \++i )  
58![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
59![InBlock.gif][]for ( int j = i\+1; j < n; \++j )  
60![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
61![InBlock.gif][] F( word\[i\], word\[j\], i, j );  
62![ExpandedSubBlockEnd.gif][] \}  
63![ExpandedSubBlockEnd.gif][] \}  
64![InBlock.gif][]  
65![InBlock.gif][]for ( int i =1; i < n; \++i )  
66![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
67![InBlock.gif][] result \+= dp\[i\]\[i\-1\];  
68![ExpandedSubBlockEnd.gif][] \}  
69![InBlock.gif][]if ( result > max ) max = result;  
70![InBlock.gif][]  
71![InBlock.gif][]while ( next\_permutation( id.begin(), id.end() ) )  
72![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
73![InBlock.gif][] result =0;  
74![InBlock.gif][]for ( int i =1; i < n; \++i )  
75![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]![dot.gif][]\{  
76![InBlock.gif][] result \+= dp\[id\[i\]\]\[id\[i\-1\]\];  
77![ExpandedSubBlockEnd.gif][] \}  
78![InBlock.gif][]if ( result > max ) max = result;  
79![ExpandedSubBlockEnd.gif][] \}  
80![InBlock.gif][] printf( "%d\\n",max );  
81![InBlock.gif][] word.clear();  
82![InBlock.gif][] id.clear();  
83![ExpandedSubBlockEnd.gif][] \}  
84![InBlock.gif][]  
85![InBlock.gif][]return0;  
86![ExpandedBlockEnd.gif][]\}

转载于:https://www.cnblogs.com/PureMilk/archive/2008/07/17/1245085.html

[http_acm.pku.edu.cn_JudgeOnline_problem_id_2817]: http://acm.pku.edu.cn/JudgeOnline/problem?id=2817
[ContractedBlock.gif]: https://www.cnblogs.com/Images/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/a0d6118596be4206a71913028486f9f4.png
[None.gif]: /images/20220109/f4d8868bc706417aa666c99cc9f594e0.png
[dot.gif]: /images/20220109/e5db7cd9aaf846c68d97c88700cda37a.png
[InBlock.gif]: /images/20220109/7f3a96278a16400c989711670fa6a851.png
[ExpandedSubBlockStart.gif]: https://www.cnblogs.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif
[ContractedSubBlock.gif]: https://www.cnblogs.com/Images/OutliningIndicators/ContractedSubBlock.gif
[ExpandedSubBlockEnd.gif]: /images/20220109/e048321fb08747a6b02beb1644d6dbbc.png
[ExpandedBlockEnd.gif]: /images/20220109/804c5ea2d2714f27a6f2797d57b185c2.png