写暴搜WA了,数据也看不了,求助
查看原帖
写暴搜WA了,数据也看不了,求助
209168
FelFa_1414666楼主2022/1/30 14:04

为什么为什么为什么为什么为什么

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second
using namespace std;
const int INF=1e9+7;
int n,mn;
map<string,int> mem;
string s[25],ans;
bool cmp(string a,string b)
{
	int ma=a.size(),mb=b.size();
	for(int i=0;i<min(ma,mb);i++)
	{
		if (a[i]<b[i])
			return true;
		else if (a[i]>b[i])
			return false;
	}
	return ma<mb;
}
bool prefix(string s2,string s1)
{
	if ((int)s1.size()>(int)s2.size())
		return false;
	string ns=s2.substr(0,(int)(s1.size()));
	return ns==s1;
}
string mi(string s2,string s1)
{
	return s2.substr((int)(s1.size()));
}
void print(string s)
{
	for(int i=0;i<s.size();i++)
	{
		if (i%20==0&&i)
			cout<<endl;
		putchar(s[i]);
	}
	cout<<endl<<endl;
}
void dfs(int len,string ds,string s1)
{
	int ld=ds.size();
	if (len+ld>=mn)//最优性剪枝 
		return;
	if (ds==""&&s1!="")
	{
		if (len<mn||(len==mn&&cmp(s1,ans)))
		{
			mn=len;
			ans=s1;
		}
		return;
	}
	if (mem.count(ds)&&mem[ds]<=len)
		return;
	mem[ds]=len;
	for(int i=0;i<n;i++)
	{
		int m=s[i].size();
		if (prefix(ds,s[i]))
			dfs(len+m,mi(ds,s[i]),s1+s[i]);
		else if (prefix(s[i],ds))
			dfs(len+ld,mi(s[i],ds),s1+ds);
	}
}
void run(int codenum)
{
	mem.clear();
	mn=INF;
	for(int i=0;i<n;i++)
		cin>>s[i];
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if (i!=j&&prefix(s[i],s[j]))
				dfs((int)(s[j].size()),mi(s[i],s[j]),s[j]);
	cout<<"Code "<<codenum<<": "<<mn<<" bits"<<endl;
	print(ans);
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(NULL);
	int TT=0;
	while(1)
	{
		cin>>n;
		if (n==0)
			break;
		run(++TT);
	}
	return 0;
}
2022/1/30 14:04
加载中...