115、单词数最多的关联文本.docx

解题思路

首先要理解题目中对于“关联文本”的定义——第一个单词以外，每个单词的首字母都与前一个字母的末尾字母相同，也就是说“单词接龙”。

而本题要求我们在一个字符串数组?word?中，挑出其中任意个字符串并以任意顺序组成一段字符串数量最多的关联文本。

本题考察的难点在于“以任意顺序”这一条件。如果我们将其改为“不改变相对顺序”，本题会是一个十分典型的动态规划题目。

既然如此，那就让我们先将“以任意顺序”这一条件改为“不改变相对顺序”。那么本题的状态可以定义dp[i][c]?，表示从?word[0]?到?word[i]?这一闭区间内组成以?cc?结尾的关联文本所能使用的最多的字符串数。类似于?01?背包，对于word[i]?我们有“选”与“不选”两种选择。不选的话，dp[i][c]=dp[i?1][c]?；选的话，dp[i][last]=dp[i?1][first]+1?，first?表示?word[i]?的首字母，?last表示word[i]last表示word[i]?的末尾字母，对于?last?以外的?cc?，其状态并不会改变，依然是?]dp[i][c]=dp[i?1][c]?。

现在让我们回到原本的条件来。可以看到，如果不改变相对顺序，?dp[i]?只能由?dp[i?1]?转移而来，这意味着我们最后选择的只能是?word[i]?，这对于实现“任意顺序”是肯定不够的，所以我们可以使用状态压缩来丰富?dp?数组所表示的状态信息。

可以使用二进制数bits?替代原本的?i?来表示可以选择的字符串范围，再枚举?bits?中为?11?的位数，如果第k?位为?1?，就可以将?word[k]?作为最后一个选择的字符串，得到状态转移方程：

)dp[bits][last]=max(dp[bits][last],dp[bits⊕(1k)][first]+1)

状态转移方程中的?first?为?word[k]?首字母，last?为?word[k]?末尾字母，\oplus⊕?为异或运算符号。

本题解的时间复杂度为?O(2^n\timesn)O(2n×n)?。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

intmain()

{

intn;

cinn;

vectorstringword(n);

vectorintfirst(n),last(n);

vectorvectorintdp(1n,vectorint(26,0));

for(inti=0;in;i++){

cinword[i];

first[i]=word[i][0]-a;

last[i]=word[i].back()-a;

}

for(intbits=0;bits(1n);bits++){

for(inti=0;in;i++){

if(bits(1i)){

dp[bits][last[i]]=max(dp[bits][last[i]],dp[bits^(1i)][first[i]]+1);

}

}

}

intres=0;

for(inti=0;i26;i++){

res=max(res,dp[(1n)-1][i]);

}

coutresendl;

return0;

}