DFS 90分 如何优化
查看原帖
DFS 90分 如何优化
1050776
peterJr楼主2025/1/31 14:51

RT

#include <bits/stdc++.h>

using namespace std;

int ans = 1e8;
string s;
long long n;

void dfs(int k, long long x, int p, long long t)
{
	if (p > ans) return ;
	if (t > n) return ;
	if (k > s.size() - 2) 
	{
		if (t + x == n) ans = min(ans, p);
		return ;
	}
	
	dfs(k + 1, s[k + 1] - '0', p + 1, t + x);
	dfs(k + 1, x * 10 + (s[k + 1] - '0'), p, t);
}

int main()
{
	cin >> s >> n;
	
	dfs(0, s[0] - '0', 0, 0);
	
	if (ans != 1e8) cout << ans << endl;
	else cout << -1 << endl;
	
	return 0;
}
2025/1/31 14:51
加载中...