P1278

ULGANOY · 2023-02-02 11:03:21 · 个人记录

单词游戏

题目描述

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

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

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

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

5
IOO
IUUO
AI
OIOOI
AOOI

样例输出 #1

16

状态压缩优化搜索

开个状压记录单词使用的状态 这样记忆化才没有后效性

还是学正解 别依赖信仰剪枝

#include<bits/stdc++.h>
using namespace std;
int n,maxx=0;
map<char,int>ma;
int vis[20];int f[20][(1<<17)];
string s[20];int l[20];
int tim=0;
int dfs(int now,int state)
{
    if(f[now][state])return f[now][state];
    int ans=0;
    for(int i=1;i<=n;i++)
        if(i!=now&&s[i][0]==s[now][l[now]-1]&&!(state&(1<<(i-1))))
            ans=max(ans,dfs(i,state|(1<<(i-1))));
    return f[now][state]=ans+l[now];
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i],l[i]=s[i].size();
    ma['A']=1,ma['E']=2,ma['I']=3,ma['O']=4,ma['U']=5;
    for(int i=1;i<=n;i++)
        maxx=max(maxx,dfs(i,(1<<(i-1))));
    cout<<maxx<<"\n";
    return 0;
}