首页 > 代码库 > hust 1075 Every String Left Behind

hust 1075 Every String Left Behind

2024-07-04 06:46:57   224人阅读

题目描述

Elenore has a list of strings that she wants to put in a file. She could just put them all into a file in order, but she wants to minimize the size of the file. So she figures she can combine all the strings into one large string which contains the original strings as substrings. Then for each string she just needs to store the index and length of the string. For example, let‘s say the strings she needs to store are: ? doghouse ? houseboat ? corndog Then Elenore can make the string "corndoghouseboat" that contains all the input strings.

输入

There will be several test cases. Each test case will start with a line with a positive integer, N, that is at most 20. Then N lines will follow each containing a string. The strings will consist of only lowercase letters.

输出

For each test case, output a line that says "Elenore can use a string of length L." where L is the length of the shortest string that contains all of the input strings.

样例输入

3
doghouse
houseboat
corndog
1
hello
4
department
of
redundancy
department

样例输出

Elenore can use a string of length 16.
Elenore can use a string of length 5.
Elenore can use a string of length 22.

这是一个状态压缩dp题，可是我超时了，o（2^nn^2）的时间复杂度，过路的朋友帮忙看看怎么优化
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
 
int state[1<<20+1];
char str[21][100],stri[100],strj[100];
int len[21],a[21][21];
 
void init(int n)
{
    for(int i=0;i<=1<<n;i++)
    state[i]=99999999;
    for (int i=0;i<n;i++)
    state[1<<i]=len[i];
    state[0]=0;
}
 
void strccmmpp(int n)
{
    int temp;
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    {
        if (i==j) a[i][j]=0;
        else if(i!=j)
        {
            temp=len[j];
            for (int l=0;l<len[j];l++)
            {
                strj[l]=str[j][l];
                strj[l+1]=NULL;
                int l1=0;
                bool cut=true;
                for (int k=len[i]-l-1;k<len[i];k++)
                if (strj[l1++]!=str[i][k]) {cut=false;break;}
                if (cut) {temp-=l+1;break;}
                if (l1>=len[j]) break;
            }
            a[i][j]=temp;
        }
    }
}
 
int main()
{
    int n;
    while (scanf("%d",&n)!=EOF)
    {
        gets(stri);
        for (int i=0;i<n;i++)
        {
            gets(str[i]);
            len[i]=strlen(str[i]);
        }
        init(n);
        strccmmpp(n);
        for (int s=0;s<(1<<n);s++)
        {
            for (int i=0;i<n;i++)
            if (s & (1<<i))
            {
                for (int j=0;j<n;j++)
                if ((s & (1<<j))==0)
                {
                    state[s|(1<<j)]=min(state[s]+a[i][j],state[s|(1<<j)]);
                }
            }
        }
        printf("Elenore can use a string of length %d.\n",state[(1<<n)-1]);
    }
    return 0;
}

 


联系
我们