题解 P1278 【单词游戏】

## 前言 首先，看到这道题目，我首先想到的是暴搜，通过$vector$来搞，代码也是很短的。 这里用了一个类似于分治的思想 把一个大问题转化为小问题 先枚举第一个单词，之后把能拼接在它后面的单词都一个一个的去试，哪个最优选哪个 ```cpp #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; } ``` [然后](https://www.luogu.org/record/27279213)，你会发现你只得了70分，开$O(2)$试试？[TLE](https://www.luogu.org/record/27279276)again! 想一想更优秀的算法，加记忆化？是的！ ## 正文 ### 储存状态 如何存状态 我们发现每一个字符串的状态都要么是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$ 那么判断这个单词是否用过，我们就可以这么写 ```cpp if(!((y>>(i-1)&1))//按位与，只有两个数这一位都是1才为1，所以只有当最后一位是1，这个数才会是1，否则是0 ``` ### 标记状态 如何将这一位变成$1$ 将这一位变成$1$，我们可以用位运算中的按位或——两位都是$0$，这一位的得数才为$0$ ```cpp y|(1<<(i-1)) ``` 这应该是很显然的 ### 总结 现在就可以看总的代码了 ```cpp #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$，快了不只一点。但是空间确实消耗很大。 编程中有很多算法，用空间换时间，记忆化搜索就是这么一个代表，我们要学习这种思想，想出更巧妙的办法！