UVa 1204 Fun Game

题目

◇题目传送门◆（由于UVa较慢，这里提供一份vjudge的链接）
◇题目传送门（vjudge）◆

题目大意

一些小孩（至少有两个）围成一圈做游戏。每轮从某个小孩开始往他左边或者右边传手帕。当一个小孩拿到手帕后会在上面写下自己的性别，男孩写B，女孩写G，然后按同一方向继续传下去。每轮可在任何一个小孩写完后停止。现在游戏已经进行了$N$轮，已知每轮手帕上的字，求最少可能有几个小孩。

思路

首先我们不难发现，当一个字符串完全包含于另一字符串，则这个串对于答案便没有影响。所以我们就可以使用预处理处理掉这些字符串。

我们不妨考虑一个简化的版本。小孩排成一行。且传手帕都是从左到右传的。那么这个问题就可以转换为：找出一个最短的序列，使得所有的串都是它的连续子串。

不难想到一个简单的算法：每次选一个串，将它接在当前最后一个串的尾部。因为之前已经排除了完全包含的情况，所以每次选的串的头部一定可以和上一个串的尾部重合，并且露出一部分。

则最终得到的串的长度就等于所有串的长度之和减去每个串（除去第一个）与前一个串的最大重叠长度。

上面这个算法启发我们使用DP来解决。

我们定义状态$f(s,i)$为当前已经选择的字符串集合为$s$，最后一个串为$i$的可减去重叠部分的总长。

则不难列出状态转移方程：

其中$j$为加进去的串，$c(i,j)$为将串$j$与串$i$的最大重叠长度。

我们再将原问题与这个简化版的问题进行对比。

原问题中，有两个不同的方向。因此我们在选串之后，应考虑是否将它直接接在当前串的尾部，还是倒过来接上去。所以状态$f(s,i)$中的$i$就有$2N$种可能，每次的决策也变成$2N$个。

原问题中，由于小孩是围成一个圈的，所以我们可以规定第一个串的正向串放在最前面，在结束后检查一下所有的ii<script type="math/tex" id="MathJax-Element-1064">i</script>为全集的状态，并考虑第一个串和最后一个串的重叠部分即可。

细节部分详见代码。

正解代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;const int Maxn=16;string s[Maxn+5][2];
int N,len[Maxn+5];
int same[Maxn+5][Maxn+5][2][2];
int f[(1<<Maxn)+5][Maxn+5][2];struct Node {string s,rev;bool operator < (const Node rhs) const {return s.length()<rhs.s.length();}
}t[Maxn+5];int GetSame(string &a,string &b) {int len1=a.length();int len2=b.length();for(int i=1;i<len1;i++) {if(len2+i<=len1)continue;bool ok=true;for(int j=0;i+j<len1;j++)if(a[i+j]!=b[j]) {ok=false;break;}if(ok)return len1-i;}return 0;
}//计算两个串的重叠部分长度void Prepare() {sort(t,t+N);int cnt=0;for(int i=0;i<N;i++) {bool ned=true;for(int j=i+1;j<N;j++)if(t[j].s.find(t[i].s)!=string::npos||t[j].rev.find(t[i].s)!=string::npos) {ned=false;break;}if(ned) {s[cnt][0]=t[i].s,s[cnt][1]=t[i].rev;len[cnt]=t[i].s.length();cnt++;}}//排除一个串包含于另一个串的情况N=cnt;for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int x=0;x<2;x++)for(int y=0;y<2;y++)same[i][j][x][y]=GetSame(s[i][x],s[j][y]);//预处理任意两个串（正向和反向）的重叠部分
}void update(int &x,int val) {if(x<0||val<x)x=val;
}
void Solve() {memset(f,-1,sizeof f);f[1][0][0]=len[0];int S=(1<<N)-1;for(int s=1;s<S;s++)for(int i=0;i<N;i++)for(int x=0;x<2;x++)if(f[s][i][x]>=0)for(int j=1;j<N;j++)if(!(s&(1<<j)))for(int y=0;y<2;y++)update(f[s|1<<j][j][y],f[s][i][x]+len[j]-same[i][j][x][y]);int ans=-1;for(int i=0;i<N;i++)for(int x=0;x<2;x++) {if(f[S][i][x]<0)continue;update(ans,f[S][i][x]-same[i][0][x][0]);}//检查为全集时的状态ans=max(ans,2);//注意题目中明确说明至少有2个小孩，所以当求出答案为1时应输出2printf("%d\n",ans);
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifwhile(scanf("%d",&N)!=EOF&&N) {for(int i=0;i<N;i++) {cin>>t[i].s;t[i].rev=t[i].s;reverse(t[i].rev.begin(),t[i].rev.end());}Prepare();Solve();}return 0;
}