求助,4,11wa,实在不知道改哪里了
查看原帖
求助,4,11wa,实在不知道改哪里了
574945
SCAU_anpuren楼主2021/12/13 21:33
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s;
int n;
int h;
int min1 = 0x3f3f3f;
void dfs(int i, int sum1, int count1)
{
	//cout <<sum1 <<' '<<count1<< endl;
	if ((sum1 == h && count1)) { if (i != n - 1) { min1 = min(min1, count1 + 1); return; } else min1 = min(min1, count1); }
	else if (sum1 == h && !count1&&!s[i+1]) {min1=min(min1,1); return ;}
	else if (sum1 > h) return;
	long long  sum = 0;
	int pd = 0;
	for (int x = i+1; x < n; x++)
	{
		//cout << sum << endl;
		if (!pd && !s[x]) continue;
		pd = 1;
		sum = sum * 10 + s[x] - '0';
		if (sum+sum1 <= h) dfs(x, sum+sum1, count1 + 1),pd=0;
		//else if (sum == sy) min1 = min(min1, count1);
		else break;
	}
	
}
int main()
{
	cin >> s >> h;
	 int pd = 0;
	 long long sum = 0;
	 n = s.size();
	 long long sum2 = 0;
	for (int i = 0; i < n; i++)
	{
		sum2 += s[i] - '0';
		if (!pd && !s[i]) continue;
		pd = 1;
		//if(s[i]-'0')
			sum = sum * 10 + s[i] - '0';
	}
	if (sum2 > h) { cout<<-1;; return 0; }
	if (sum == h) { cout << '0'; return 0; }
	sum = 0;
	pd = 0;
	for (int i = 0; i < n; i++)
	{
		if (!pd && !s[i]) continue;
		pd = 1;
		sum = sum * 10 + s[i] - '0';
		if (sum <= h) { if (!i) dfs(i, sum, 0); else dfs(i, sum, 0); pd = 0; }
		else break;
	}
	if(min1!=0x3f3f3f)
	cout << min1;
	else cout<<-1;;
}
2021/12/13 21:33
加载中...