学步园

这道题,居然用错误的方法也可以AC,好吧,我看了比人写的代码,自己弄个数据进去了,好多wa了.

http://poj.org/problem?id=1699

题意是给你很多子序列,让你求最短父序列.

先说这道题的思路:

先预处理出来每两个子序列a,b,a添加到b后面最少添加多少个字符,并保存到add[a][b].

用dfs处理一下,枚举顺序,既然我们已经枚举顺序了,所以我们dfs的时候只需考虑b加到a后面就可以了,那a加到b后面的情况呢?因为是dfs所以肯定会遍历到,所以

我们只要默认添加在后面就好啦

为什么这样的算法可以呢?我一开始是感觉不可以的

以为这个是两两判断的所以

例如这个数据

3

ABC

A

B

这样就会出错,答案变成4,其实应该是5

其实我们只要这样做就可以了

dfs的时候记录这个决策前面的那个字符串的编号,为pre,如果add[pre][i] ==0  那就是说i串可以被pre串完全容纳,位置有可能是在前面,比如pre串为ABCD ,i串为ABC,

那么后面的状态还是得依靠前面的pre串,来,所以pre不改变,那么不等于0呢,ABC CD ,那当然是ABCD所以后面的要和CD比较,要特别注意这点,

虽然不注意也可以AC,估计是题的#include <iostream>

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
using namespace std;
const int MAXN=11;
bool vis[MAXN];
int n;
int len;
string str[MAXN];
int add[MAXN][MAXN];
int pos[MAXN],order[MAXN];
int cal(string &a,string &b)
{
    int alen=a.size(),blen=b.size();
    for(int i=0; i<a.size(); i++)
    {
        bool ok=true;
        for(int j=0;j<blen && i+j<alen;j++)
        {
            if(a[j+i]!=b[j])
            {
                ok=false;
                break;
            }
        }
        if(ok)
            return max(i+blen-alen,0);
    }
    return blen;
}
void dfs(int pre,int cnt,int sum)
{
    if(sum>=len) return ;
    if(cnt==n)
    {
        len=min(len,sum);
        return ;
    }
    for(int i=0; i<n; i++)
    {
        if(!vis[i])
        {
            vis[i]=true;
            if(pre!=-1)
                if(add[pre][i]!=0)
                    dfs(i,cnt+1,sum+add[pre][i]);
                else
                    dfs(pre,cnt+1,sum);
            else
                dfs(i,cnt+1,sum+str[i].size());
            vis[i]=false;
        }
    }
}
int main()
{
//    freopen("in","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        len=1<<30;
        memset(vis,0,sizeof(vis));
        scanf("%d",&n);
        for(int i=0; i<n; i++) cin>>str[i];
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(i!=j)
                    add[i][j]=cal(str[i],str[j]);
        dfs(-1,0,0);
        cout<<len<<endl;
    }
    return 0;
}