81分 #6和#11WA
查看原帖
81分 #6和#11WA
761210
dpdfs12345楼主2023/7/30 15:32
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 50;
string s;
int n,ans = 1e9;
bool st[N];
// st[i] : i and i + 1
bool check(){
	int sum = 0,t = 0,last = 0;
	for(int i=0;i<s.size()-1;i++){
		if(st[i]){
			for(int j=last;j<=i;j++) t = t * 10 + s[j] - '0';
			last = i + 1;
			sum += t;
			t = 0;
		}
	}
	t = t * 10 + s[s.size()-1] - '0';
	sum += t;
	return sum == n;
}
void dfs(int u,int cnt){
	if(u == s.size()-1){
		if(check()) ans = min(ans,cnt);
		return ;
	}
	dfs(u + 1,cnt);
	st[u] = true;
	dfs(u + 1,cnt+1);
	st[u] = false;
}
int main(){
	cin >> s >> n;
	dfs(0,0);
	if(ans == 1e9) puts("-1");
	else printf("%d",ans);
	return 0;
}
2023/7/30 15:32
加载中...