P1278单词游戏 题解

· · 个人记录

前言

看了看其他题解，得出了一个结论：我太菜了，根本看不懂。。。

经过自己一番瞎搞，竟然做出来了？！

0.基本变量

int n,ans=0; //ans是储存最终答案最大值
struct word //记录一个单词的基本信息
{
    char begin,end; //起止字符
    int size; //长度
    bool vis; //是否被搜索过
    word(){vis=0;} //初始化
}a[17];

1.暴搜过样例

首先，根据题意，我们很容易想到一种暴搜方案：

int dfs(int now,int num) //now:当前单词编号 num:之前的单词长度和
{
    int flag=a[now].end,len=num+a[now].size,res=len;
    /*
    flag:储存当前单词的终止字符，用来筛选下一个单词
    len:储存包括当前单词的单词长度和
    res:储存经过当前单词的最佳答案
    */
    a[now].vis=1; //标记
    for(int i=1;i<=n;i++)
        if(a[i].begin==flag&&!a[i].vis)
            res=max(res,dfs(i,len)); //更新最佳答案
    a[now].vis=0; //回溯
    return res; //完结
}

这样，我们就愉快地得到了70分

2.优化出奇迹

为什么会超时呢？

当数据出现形如

ABBBBBA
ABBBBA
ABBBA
ABBBBBBA
ABBBA

的数据时，我们的暴搜会把每一个都搜一遍，直接达到了最高复杂度 n! ，所以面对这种情况，我们可以用贪心的方法，对于首尾字母相同的单词，每次选最长的。

那我们肯定不能每次选单词时都算一遍最大值，于是我们进行一个sort的预处理：

bool cmp(word a,word b){return a.size>b.size;}

sort(a+1,a+n+1,cmp);

提前按照长度从大到小排序，这样就能保证拥有同样首尾字母的单词中首先被选的一定是最长的。

当我们搜索到一个单词时，面对同样尾字母的下一个单词（首字母肯定都和当前单词的尾字母一样），最长的总比短的要好，而我们通过排序已经保证了第一个选的是最长的，所以选了一个后，相同尾字母的其他单词就都不用考虑，所以我们要做一个标记，标记char done[17]，done[i]储存第i个被选中的单词尾字母，那么与它有同样尾字母的就不用选了。于是我们在搜索中加入判断

bool go_on=1;
//count是done数组的长度
for(int j=1;j<=count;j++) //遍历done数组每一个元素
    if(a[i].end==done[j]) //判断此单词的尾字母在done中出现
    {
        go_on=0;
        break;
    }

和标记

if(go_on) //如果done中没有出现该尾字母，就递归搜索，并把该尾字母加入done中
{
    res=max(res,dfs(i,len));
    done[++count]=a[i].end;
}

哦，别忘了初始化(这个不用解释了吧)

int count=0,done[17];
for(int i=1;i<=16;i++)
    done[i]='?';

这样，我们就得到了一份完整的AC代码

#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
struct word
{
    char begin,end;
    int size;
    bool vis;
    word(){vis=0;}
}a[17];
bool cmp(word a,word b){return a.size>b.size;}
int dfs(int now,int num)
{
    int flag=a[now].end,len=num+a[now].size,res=len;
    int count=0,done[17];
    for(int i=1;i<=16;i++)
        done[i]='?';
    a[now].vis=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i].begin==flag&&!a[i].vis)
        {
            bool go_on=1;
            for(int j=1;j<=count;j++)
                if(a[i].end==done[j])
                {
                    go_on=0;
                    break;
                }
            if(go_on)
            {
                res=max(res,dfs(i,len));
                done[++count]=a[i].end;
            }
        }
    }
    a[now].vis=0;
    return res;
}
int main()
{
    string s;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        a[i].begin=s[0],
        a[i].end=s[s.size()-1],
        a[i].size=s.size();
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        a[i].vis=1;
        ans=max(ans,dfs(i,0));
        a[i].vis=0;
    }
    cout<<ans<<endl;
    return 0;
}

完结撒花～