ZHK

ZHK

一只叫ZHK的蒟蒻为了RP而战

题解 P1278 【单词游戏】

posted on 2019-11-16 15:05:22 | under 题解 |

前言

首先,看到这道题目,我首先想到的是暴搜,通过 $vector$ 来搞,代码也是很短的。

这里用了一个类似于分治的思想

把一个大问题转化为小问题

先枚举第一个单词,之后把能拼接在它后面的单词都一个一个的去试,哪个最优选哪个

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
    T f=1;x=0;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    x*=f;
}//快读,常数优化
template<typename T>inline void write(T x){
    if(x<0){
        putchar('-');
        write(x*-1);
        return;
    }
    if(x>9)write(x/10);
    putchar(x%10+48);
}//快写,常数优化
string st[18];
vector<int>v[210];//动态数组
int f[18];//标记数组
int dfs(int x){
    int ans=0;
    for(auto i:v[st[x][st[x].size()-1]])//v数组是存第1个字母的一个容器
        if(!f[i]){
            f[i]=1;//标记这个字符串已经用过了
            ans=max(ans,dfs(i));//打擂
            f[i]=0;//回溯
        }
    return ans+st[x].size();
}
int main(){
    int ans=0,n;
    read(n);//读入
    for(int i=1;i<=n;i++)cin>>st[i],v[st[i][0]].push_back(i);//读入,放入vector容器
    for(int i=1;i<=n;i++){
        f[i]=1;//表记
        ans=max(ans,dfs(i));//打擂法找到最优解
        f[i]=0;//回溯
    }
    write(ans);//输出
    return 0;
}

然后,你会发现你只得了70分,开 $O(2)$ 试试?TLEagain!

想一想更优秀的算法,加记忆化?是的!

正文

储存状态

如何存状态

我们发现每一个字符串的状态都要么是0,要么是1,所以我们可以用二进制的思想去压缩状态。

$$1≤N≤16$$

$$2^{n(16)}=65536$$

开数组很充裕,浪费也不要紧。

判断状态

如何去判断第 $i$ 个单词有没有用过

从右往左这个数二进制的第 $i$ 位是 $1$ ,就代表这个单词用过,反之 $0$ 就代表这个单词没用过。

但给你这么一个数,你该这么去判断呢?

用位运算!

如果第 $i$ 为是 $1$ ,那么 $x>>(i-1)$ 后 $\mod2$ 就是 $1$

如果第 $i$ 为是 $0$ ,那么 $x>>(i-1)$ 后 $\mod2$ 就是 $0$

那么判断这个单词是否用过,我们就可以这么写

if(!((y>>(i-1)&1))//按位与,只有两个数这一位都是1才为1,所以只有当最后一位是1,这个数才会是1,否则是0

标记状态

如何将这一位变成 $1$

将这一位变成 $1$ ,我们可以用位运算中的按位或——两位都是 $0$ ,这一位的得数才为 $0$

y|(1<<(i-1))

这应该是很显然的

总结

现在就可以看总的代码了

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
    T f=1;x=0;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    x*=f;
}
template<typename T>inline void write(T x){
    if(x<0){
        putchar('-');
        write(x*-1);
        return;
    }
    if(x>9)write(x/10);
    putchar(x%10+48);
}
string st[18];
vector<int>v[210];
int f[17][1<<17];
int dfs(int x,int y){
    if(f[x][y])return f[x][y];
    int ans=0;
    for(auto i:v[st[x][st[x].size()-1]])
        if(!((y>>(i-1))&1))ans=max(ans,dfs(i,y|(1<<(i-1))));
    return f[x][y]=ans+st[x].size();
}
int main(){
    int ans=0,n;
    read(n);
    for(int i=1;i<=n;i++)cin>>st[i],v[st[i][0]].push_back(i);
    for(int i=1;i<=n;i++)ans=max(ans,dfs(i,(1<<(i-1))));
    write(ans);
    return 0;
}

刚开始我认为这应该没有多少重复运算,所以我写了个暴搜,但是,我写了记忆化之后惊奇地发现,暴搜总用时 $4.00s$ ,也就是 $4000ms$ ,而记忆化搜索总用时 $73ms$ ,快了不只一点。但是空间确实消耗很大。

编程中有很多算法,用空间换时间,记忆化搜索就是这么一个代表,我们要学习这种思想,想出更巧妙的办法!