Submission #50773377

---

Source Code Expand

#include<bits/stdc++.h>
#include<set>
using namespace std;
const int N=20;
int n,f[N][1<<N],v[N],pos,len=1e9;
string a[N],b[N],g[N][1<<N],ans;
bool cmp(string a,string b)
{
	int k=min(a.size(),b.size());
	for(int i=0;i<k;i++)
	    if(a[i]<b[i])return 1;
	    else if(a[i]>b[i])return 0;
	return a.size()<b.size();
}
int cal(string a,string b)
{
	int ret=-1;
	for(int i=min(a.size()-1,b.size()-1);i>=0;i--)
	{
		int flag=1;
		for(int j=0;j<=i;j++)
		    if(a[a.size()-1-j]!=b[i-j])flag=0;
		if(flag)
		{
			ret=i;
			break;
		}
	}
	return ret;
}
int main()
{
	memset(f,0x3f,sizeof(f));
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	    cin>>b[i];
	for(int i=0;i<n;i++)
	    for(int j=i+1;j<n;j++)
	    {
	    	if(b[i].find(b[j])!=-1)v[j]=1;
	    	else if(b[j].find(b[i])!=-1)v[i]=1;
		}
	for(int i=0;i<n;i++)
	    if(!v[i])a[pos++]=b[i];
	sort(a,a+pos,cmp);
	for(int i=0;i<pos;i++)
	    f[i][1<<i]=a[i].size(),g[i][1<<i]=a[i];
	//printf("%d\n",pos);
	for(int j=0;j<1<<pos;j++)
	    for(int i=0;i<pos;i++)
	        if(f[i][j]<1e9)
	        {
	        	for(int t=0;t<pos;t++)
	               if(((j>>t)&1)==0)
	               {
	               	int p=cal(g[i][j],a[t]);
	               	//cout<<g[i][j]<<' '<<a[t]<<' '<<p<<'\n';
	               	if(f[i][j]+(a[t].size()-1-p)<f[t][j|(1<<t)])
	               	{
	               		f[t][j|(1<<t)]=f[i][j]+(a[t].size()-1-p);
	               		g[t][j|(1<<t)]=g[i][j];
	               		for(int h=p+1;h<a[t].size();h++)
	                        g[t][j|(1<<t)]+=a[t][h];
	                    //cout<<g[t][j|(1<<t)]<<'\n';
					}
					else if(f[i][j]+(a[t].size()-1-p)==f[t][j|(1<<t)])
					{
						string r=g[i][j];
						for(int h=p+1;h<a[t].size();h++)
	                        r+=a[t][h];
	                    if(cmp(r,g[t][j|(1<<t)]))g[t][j|(1<<t)]=r;
					}
	               	    
				   }
			}       
	for(int i=0;i<pos;i++)
	    if(len>f[i][(1<<pos)-1])len=f[i][(1<<pos)-1],ans=g[i][(1<<pos)-1];
	    else if(len==f[i][(1<<pos)-1])
	    {
	    	if(cmp(g[i][(1<<pos)-1],ans))ans=g[i][(1<<pos)-1];
		}
	cout<<ans.size();
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:40:35: warning: comparison of integer expressions of different signedness: ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   40 |                 if(b[i].find(b[j])!=-1)v[j]=1;
      |                    ~~~~~~~~~~~~~~~^~~~
Main.cpp:41:40: warning: comparison of integer expressions of different signedness: ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   41 |                 else if(b[j].find(b[i])!=-1)v[i]=1;
      |                         ~~~~~~~~~~~~~~~^~~~
Main.cpp:58:53: warning: comparison of integer expressions of different signedness: ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   58 |                         if(f[i][j]+(a[t].size()-1-p)<f[t][j|(1<<t)])
      |                            ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
Main.cpp:62:48: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   62 |                                 for(int h=p+1;h<a[t].size();h++)
      |                                               ~^~~~~~~~~~~~
Main.cpp:66:74: warning: comparison of integer expressions of different signedness: ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   66 |                                         else if(f[i][j]+(a[t].size()-1-p)==f[t][j|(1<<t)])
      |                                                 ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:69:64: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   69 |                                                 for(int h=p+1;h<a[t].size();h++)
      |                                                               ~^~~~~~~~~~~~
Main.cpp:34:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~

Judge Result