P1278 单词游戏

题目描述

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

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

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

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

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

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1： 

5
IOO
IUUO
AI
OIOOI
AOOI

输出样例#1： 

16

Solution：

　　裸的状压dp，转移也比较常规，用2进制表示串是否被用，并且记录一下当前状态下所在的串以便于转移。

代码：

#include<bits/stdc++.h>
#define il inline
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
using namespace std;
int n,len[20],w[20][20],ans;
struct node{
    int v,pos;
}f[1<<17];
char s[20][2],t[200];

int main(){
    scanf("%d",&n);
    For(i,1,n){
        scanf("%s",t);
        len[i]=strlen(t),s[i][0]=t[0],s[i][1]=t[len[i]-1];
        f[1<<i-1].v=len[i],f[1<<i-1].pos=i;
        ans=max(ans,len[i]);
    }
    For(i,1,n) For(j,1,n) if(s[i][1]==s[j][0]&&i!=j) w[i][j]=1;
    For(i,1,(1<<n)-1)
        if(f[i].v)
        For(j,1,n)
            if(w[f[i].pos][j]&&!(i&1<<(j-1)))
                if(len[j]+f[i].v>f[i|(1<<(j-1))].v){
                    f[i|(1<<(j-1))].v=len[j]+f[i].v;
                    f[i|(1<<(j-1))].pos=j;
                    ans=max(ans,f[i|(1<<(j-1))].v);
                }
    cout<<ans;
    return 0;
}