P1278 单词游戏【洛谷算法习题】

P1278 单词游戏

网页链接

P1278 单词游戏

题目描述

Io 和 Ao 在玩一个单词游戏。

他们轮流说出一个仅包含元音字母的单词，并且后一个单词的第一个字母必须与前一个单词的最后一个字母一致。

游戏可以从任何一个单词开始。

任何单词禁止说两遍，游戏中只能使用给定词典中含有的单词。

游戏的复杂度定义为游戏中所使用的单词长度总和。

编写程序，求出使用一本给定的词典来玩这个游戏所能达到的游戏最大可能复杂度。

输入格式

输入文件的第一行，包含一个自然数N ( 1 ≤ N ≤ 16 ) N(1 \le N \le 16)N(1≤N≤16)，N NN表示一本字典中包含的单词数量。以下的每一行包含字典中的一个单词，每一个单词是由字母A、E、I、O和U组成的一个字符串，每个单词的长度将小于等于100 100100，所有的单词是不一样的。

输出格式

输出文件仅有一行，表示该游戏的最大可能复杂度。

输入输出样例 #1

输入 #1

5 IOO IUUO AI OIOOI AOOI

输出 #1

16

解题思路

本题是状压 DP + 记忆化搜索的经典问题。给定N NN个仅由元音字母组成的单词（N ≤ 16 N \le 16N≤16），要求将它们排列成一个序列，使得后一个单词的首字母等于前一个单词的尾字母，每个单词最多使用一次，求所有单词长度之和的最大值。

1. 问题等价转化

• 将每个单词视为一个节点，若单词A AA的尾字母等于单词B BB的首字母，则存在一条从A AA到B BB的有向边。游戏的目标是在这个有向图中找到一条不重复经过节点的路径，使得路径上所有单词的长度之和最大。
• 由于N ≤ 16 N \le 16N≤16，可以使用二进制状态压缩表示已经使用过的单词集合。状态总数为2 16 × 16 ≈ 10 6 2^{16} \times 16 \approx 10^6216×16≈106，完全可行。
• 定义dfs(x, mask)表示当前以第x xx个单词结尾，已使用的单词集合为mask时，能继续获得的最大长度总和。

2. 状态设计

• x：当前最后一个单词的编号（1 到N NN）。
• mask：二进制掩码，第i ii位为 1 表示第i ii个单词已经被使用。
• 记忆化数组f[x][mask]存储该状态的最大后续长度。

3. 状态转移

• 对于当前单词x，取其尾字母last = s[x].back()。
• 遍历所有以该尾字母开头的单词（通过预处理的邻接表v[last]快速找到）。
• 对于每个候选单词i：
  • 若i尚未在mask中使用（即mask的第i位为 0），则可以接在x之后。
  • 递归调用dfs(i, mask | (1 << (i-1)))，获得从i继续的最大长度。
  • 取所有候选中的最大值。
• 最终返回当前单词长度 + 后续最大值。
• 若没有可接的单词，后续最大值为 0。

4. 初始调用

• 由于游戏可以从任意单词开始，需要枚举每个单词作为起点，调用dfs(i, 1 << (i-1))，取所有起点的最大值作为答案。

5. 复杂度分析

• 状态数：N × 2 N ≤ 16 × 65536 ≈ 10 6 N \times 2^N \le 16 \times 65536 \approx 10^6N×2N≤16×65536≈106。
• 转移：每个状态最多枚举N NN个候选单词，总运算量约N 2 × 2 N ≈ 1.6 × 10 7 N^2 \times 2^N \approx 1.6 \times 10^7N2×2N≈1.6×107，在 1 秒内可以完成。
• 空间复杂度：记忆化数组f[17][1<<17]约1.1 × 10 6 1.1 \times 10^61.1×106个long long，空间约 9MB，满足 256M 限制。

总结

利用状态压缩表示单词的使用情况，结合记忆化搜索枚举所有可能的单词序列，避免重复计算。通过预处理每个尾字母对应的候选单词列表，加速状态转移。最终从所有可能的起点出发取最大值即为答案。该方法简洁高效，是解决小规模排列优化问题的标准思路。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;string s[18];vector<ll>v[210];ll f[17][1<<17];lldfs(ll x,ll y){if(f[x][y])returnf[x][y];ll r=0;for(autoi:v[s[x][s[x].size()-1]]){if(!((y>>(i-1))&1))r=max(r,dfs(i,y|(1<<(i-1))));}returnf[x][y]=r+s[x].size();}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cin>>n;for(ll i=1;i<=n;i++){cin>>s[i];v[s[i][0]].push_back(i);}ll ans=0;for(ll i=1;i<=n;i++)ans=max(ans,dfs(i,(1<<(i-1))));cout<<ans;return0;}