Io和Ao在玩一个单词游戏。
他们轮流说出一个仅包含元音字母的单词，并且后一个单词的第一个字母必须与前一个单词的最后一个字母一致。
游戏可以从任何一个单词开始。
任何单词禁止说两遍，游戏中只能使用给定词典中含有的单词。
游戏的复杂度定义为游戏中所使用的单词长度总和。
编写程序，求出使用一本给定的词典来玩这个游戏所能达到的游戏最大可能复杂度。
输入格式：
输入文件的第一行，表示一个自然数N(1≤N≤16)，N表示一本字典中包含的单词数量以下的每一行包含字典中的一个单词，每一个单词是由字母A、E、I、O和U组成的一个字符串，每个单词的长度将小于等于100，所有的单词是不一样的。
输出格式：
输出文件仅有一行，表示该游戏的最大可能复杂度。
输入样例#1：
5 IOO IUUO AI OIOOI AOOI
输出样例#1：
16
子集dp，f[i][j]表示当前状态为i开头为j的最长长度，记搜水过。
#include<bits/stdc++.h> using namespace std; const int Maxn=17; string s[Maxn]; int n,tot,len[Maxn],f[1<<Maxn][5]; int decode(char c){ if(c=='A')return 0;if(c=='E')return 1;if(c=='I')return 2;if(c=='O')return 3;if(c=='U')return 4; } int DFS(int state,int str){ if(!state)return 0; if(~f[state][str])return f[state][str]; int ret=0; for(int i=0;i<n;++i){ if((state&(1<<i))&&(decode(s[i+1][0])==str)){ int S=state^(1<<i); for(int X=S;X>=0;X=(X-1)&S){ ret=max(ret,DFS(X,decode(s[i+1][len[i+1]-1]))+len[i+1]); if(X==0)break; } } } return f[state][str]=ret; } int main(){ cin>>n;tot=1<<n; for(int i=1;i<=n;++i){ cin>>s[i]; len[i]=s[i].length(); } memset(f,-1,sizeof(f)); int Ans=0; for(int i=0;i<5;++i) Ans=max(Ans,DFS(tot-1,i)); cout<<Ans<<endl; return 0; }
