洛谷 1019 单词接龙

╰+哭是因爲堅強的太久メ 2021-12-10 03:59 278阅读 0赞

![1215829-20190709234340382-103483374.png][]

【题解】

入门搜索题。

先n方枚举每对单词，计算他们接龙可以让长度延长多少，可以延长的在链式前向星中加边。

搜索的时候按照边表逐个扩展就好了。

【代码】

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define LL long long
    #define rg register
    #define N 1010
    using namespace std;
    int n,ans,tot,last[N],len[N],v[N];
    char a[N][N],st;
    struct edge{
        int to,pre,del;
    }e[200010];
    inline int read(){
        int k=0,f=1; char c=getchar();
        while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
        while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();
        return k*f;
    }
    inline void calc(int x,int y){
        int st=max(2,len[x]-len[y]+2),del=0;
        // printf("%d %d %d\n",x,y,st);
        for(rg int i=st;i<=len[x];i++){
            bool ok=1;
            for(rg int j=1;j<=len[x]-i+1;j++)if(a[x][i+j-1]!=a[y][j]){
                ok=0; break;
            }
            if(ok) del=len[y]-(len[x]-i+1);
        }
        if(del>0){
            e[++tot]=(edge){y,last[x],del}; last[x]=tot;
            // printf("[%d %d del=%d]\n",x,y,del);
        }
    }
    void dfs(int now,int lenth){
        ans=max(ans,lenth);
        for(rg int i=last[now],to;i;i=e[i].pre)if(v[to=e[i].to]<2){
            v[to]++;
            dfs(to,lenth+e[i].del);
            v[to]--;
        }
    }
    int main(){
        n=read();
        for(rg int i=1;i<=n;i++){scanf("%s",a[i]+1); len[i]=strlen(a[i]+1);}
        st=getchar(); while((!('a'<=st&&st<='z'))&&(!('A'<=st&&st<='Z'))) st=getchar();
        // for(rg int i=1;i<=n;i++) printf("[%s]\n",a[i]+1);
        for(rg int i=1;i<=n;i++)
            for(rg int j=1;j<=n;j++) calc(i,j);
        for(rg int i=1;i<=n;i++)if(a[i][1]==st){
            v[i]++; dfs(i,len[i]); v[i]--;
        }
        printf("%d\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/DriverLao/p/11161284.html

[1215829-20190709234340382-103483374.png]: /images/20211209/b9f85f64eba145b8a71c5876947df708.png