跳至正文

1 条题解

  • 0
    @ 2026-10-2 2:21:40

    使用长度严格小于两端单词的最短有效重叠,每个输入词至多使用两次,并包含单字母初始龙。

    #include <bits/stdc++.h>
    using namespace std;
    int n,best;vector<string>w;vector<vector<int>>overlap;vector<int>used;void dfs(int last,int length){best=max(best,length);int bound=length;for(int j=0;j<n;j++)bound+=(2-used[j])*max(0,int(w[j].size())-1);if(bound<=best)return;for(int j=0;j<n;j++)if(used[j]<2&&overlap[last][j]){used[j]++;dfs(j,length+int(w[j].size())-overlap[last][j]);used[j]--;}}int main(){cin>>n;w.resize(n);used.resize(n);for(auto&s:w)cin>>s;char first;cin>>first;overlap.assign(n,vector<int>(n));for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=1;k<min(w[i].size(),w[j].size());k++)if(w[i].substr(w[i].size()-k)==w[j].substr(0,k)){overlap[i][j]=k;break;}for(int i=0;i<n;i++)if(w[i][0]==first){used[i]=1;dfs(i,w[i].size());used[i]=0;}cout<<best<<"\n";}
    
    • 1

    信息

    ID
    3896
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    递交数
    0
    已通过
    0
    上传者