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;}

相关新闻

中学技校网站ASP整站源码:IIS部署与二次开发实战指南

中学技校网站ASP整站源码:IIS部署与二次开发实战指南

简介&#xff1a;这是一套面向中学、技校及职业院校的整站ASP网站源码&#xff0c;适合需要快速搭建校园门户的开发者、教师或学生参考使用。资源包共167个文件&#xff0c;以101个asp动态页面为核心&#xff0c;配合26个gif与14个jpg图片素材、7个swf动画、5个htm与4个html静态…

2026/11/18 18:36:39 阅读更多 →
STM32F407驱动AD9854:电赛扫频与寄存器配置高频考点解析

STM32F407驱动AD9854:电赛扫频与寄存器配置高频考点解析

简介&#xff1a;本资源面向参加电子设计竞赛或学习STM32嵌入式开发的学生与工程师&#xff0c;提供基于STM32F407与HAL库驱动AD9854 DDS模块输出正弦波并实现扫频功能的完整工程。信号源在扫频仪、阻抗分析仪中应用广泛&#xff0c;相比单片机DAC或FPGA ROM方案&#xff0c;AD…

2026/11/19 2:09:49 阅读更多 →
亚马逊新手开广告总踩坑?实时查竞价,帮你告别盲目出价

亚马逊新手开广告总踩坑?实时查竞价,帮你告别盲目出价

很多亚马逊新手上架新品之后&#xff0c;最焦虑的就是广告。选品的时候只算了拿货、头程、平台佣金&#xff0c;完全没预估广告点击成本&#xff1b;等到上架开广告&#xff0c;出价全靠猜。出价给高了&#xff0c;预算半天烧光&#xff0c;ACoS一路飙升&#xff0c;订单赚的钱…

2026/11/17 19:04:22 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年&#xff0c;我大部分时间都在跟浏览器标签页打交道&#xff0c;直到第一次把桌面应用跑起来&#xff0c;才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词&#xff0c;最开始是在某段时间频繁出现在同事的讨论里&#xff0c;一个用HTML…

2026/11/18 13:59:04 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档&#xff0c;主要面向智能锁安装人员、终端用户及售后维护者&#xff0c;帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件&#xff0c;大小4.37MB&#xff0c;内容结构清晰&#xff…

2026/11/18 15:33:23 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统&#xff0c;整车要求空载跑到8m/s&#xff0c;电机转速已经拉到额定点&#xff0c;驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令&#xff0c;转速纹丝不动&#xff0c;三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/18 17:05:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年&#xff0c;用它写过嵌入式驱动、做过游戏服务端&#xff0c;也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词&#xff0c;我其实挺感慨的——这门语言的难点从来不是语法多&#xff0c;而是知识点之间的耦合太深…

2026/11/18 14:33:19 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书以PDF格式发布&#xff0c;适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开&#xff0c;先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能&#xff0c;再给出完整安装步骤&…

2026/11/18 17:05:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历&#xff1a;翻开源码注释、论文摘要或者一份专业报告&#xff0c;每个字都认识&#xff0c;连在一起却像天书。想找人聊聊&#xff0c;身边要么没人懂&#xff0c;要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型&#xff0c;几秒钟之后&a…

2026/11/18 14:13:08 阅读更多 →

日新闻

周新闻

月新闻