不知道哪里错了,求指教(dfs剪枝)
查看原帖
不知道哪里错了,求指教(dfs剪枝)
1168588
FASTergood楼主2024/9/11 21:02

不知道哪里错了,求指教

#include<iostream>  
#include<algorithm>  
#include<cstring>  
#include<queue>
#define int long long  
#define endl "\n"  
using namespace std;
typedef pair <int, int>ILL;
const int N = 205;
int n, x, y, m, t;
int a[N], b[N];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int st[N];
int ans =-1;
int cnt = 0;
string s[N];
int init(const string& s1, const string& s2) {
	for (int i = s1.size() - 1; i >= 1; i--) {
		if (s1.substr(i) == s2.substr(0, s1.size() - i))
			return s1.size() - i;
	}
	return 0;
}//这个函数没问题的
void dfs(int x,int cnt)
{
	ans = max(ans, cnt);
	cout<<ans<<endl;
	for (int i = 1;i <= n;i++)
	{
		int t=init(s[i],s[x]);
		if(st[i]==2)continue;
		if(t==0)continue;
			//cout<<cnt+s[i].size()-t<<endl;
			st[i]+=1;
		//cout<<cnt<<endl;
		dfs(i, cnt+s[i].size()-t);
			st[i]-=1;
	}
}
signed main()
{
	
	cin >> n;
	for (int i = 1;i <=n+1;i++)
	{
		cin >> s[i];	
	}
	int g;
//cout<<s[1].size()+s[2].size()-init(s[1],s[2])<<endl;
	for (int i = 1;i <= n;i++)
	{
		if (s[i].substr(0, 1) == s[n + 1])
		{
			g = i;
		}
	}
	st[g]=1;
	dfs(g, s[g].size());
	cout << ans << endl;
}
样例过不去,跑出来是22,答案是23
2024/9/11 21:02
加载中...