深搜MLE求调
查看原帖
深搜MLE求调
1023189
wangtairan114楼主2023/11/3 21:31
#include <cstring>
#include <string>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <limits.h>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)>(b)?(b):(a))
#define INF 0x3f3f3f3f
//#define ll long long
#define sc scanf
#define pr printf
#define v1 first
#define v2 second
string a[30][200005],b[30][200005],s[30],st;
int n;
int c[30];
int sum;
int maxans;
int p[60];
void dfs(int k)
{
    bool ok=0;
    for(int i=1; i <= n; i++)
    {
        if(c[i]<2)
        {
            if(k==1)
            {
                if(a[i][0]==st){
                    p[k]=i;
                    sum+=s[i].size();
                    c[i]++;
                    dfs(k+1);
                    sum-=s[i].size();
                    c[i]--;
                    ok=1;
                }
            }
            else
            {
                int maxn=0;
                int maxn2=0;
                for(int j=0; j < min(s[p[k-1]].size(),s[i].size()); j++)
                {
                    if(b[p[k-1]][j]==a[i][j])
                    {
                        maxn=j+1;
                        if(maxn2==0)
                            maxn2=maxn;
                    }
                }
                if(maxn>0){
                    if(!(maxn==min(s[p[k-1]].size(),s[i].size())&&s[p[k-1]]!=s[i]))
                    {
                        p[k]=i;
                        sum+=s[i].size()-maxn2;
                        c[i]++;
                        dfs(k+1);
                        sum-=s[i].size()-maxn2;
                        c[i]--;
                        ok=1;
                    }
                }
            }
        }
    }
    if(!ok)
    {
        maxans=max(maxans,sum);
        return;
    }
}
int main()
{
    cin  >> n;
    for(int i=1; i <= n; i++)
    {
        cin >> s[i];
        a[i][0]=s[i][0];
        for(int j=1; j < s[i].size(); j++)
        {
            a[i][j]=a[i][j-1]+s[i][j];
        }
        b[i][0]=s[i][s[i].size()-1];
        for(int j=1; j < s[i].size(); j++)
        {
            b[i][j]=s[i][s[i].size()-1-j]+b[i][j-1];
//            cout << b[i][j]<< endl;
        }
    }
    cin >> st;
    dfs(1);
    cout << maxans;
    return 0;
}

记录

2023/11/3 21:31
加载中...