Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

参考了其他人的答案,写出的!附代码

Posted by Matthew_lyns at 2017-05-05 09:31:44 on Problem 1416
#include <iostream>
using namespace std;

const int Maxsize = 1000000;

int path;    // 最优划分的划分方式
int p;      // 某种划分方式
int target;  // 目标值
int visit[Maxsize];  // 记录每个sum出现的次数,数组尽量开大一点


int sum;     // 某种划分方式的和
int result;  // 最优划分方式的和

double pow(int i, int j)  //计算幂函数
{
	double ret = 1;

	while(j--)
	{
		ret *= i;
	}
	return ret;
}

int getlen(int n)  // 得到n的位数
{
	if(n < 10)
		return 1;
	else if(n < 100)
		return 2;
	else if(n < 1000)
		return 3;
	else if(n < 10000)
		return 4;
	else if(n < 100000)
		return 5;
	else
		return 6;
}

int getvalue(char* s, int i)  // 得到数字字符串s前i位字符的数值
{
	int k = i;
	int sum = 0;
	while(k)
	{
		k--;
		sum += (s[k] - '0')*(int)pow(10, (i-k-1));
	}
	return sum;
}

int gethead(int n, int i) // 得到由n的前i位数字构成的int
{
	int len = getlen(n);
	if(len < i)
		return n;
	return n/(int)pow(10, (len - i));
}

int gettail(int n, int i)  // 得到由n的后i位数字构成的int
{
	return n % (int)pow(10,i);
}

void dfs(char* s, int len)
{
	if(len == 0)
	{
		visit[sum]++;   // 标记
		if(sum > result && sum <= target)
		{
			result = sum;
			path = p;
		}
		return;
	}
	for(int i = 1; i <= len; i++)
	{
		int a = getvalue(s, i);  // n的前i位字符转变为数字留下
		sum += a;    // 部分和
		if(sum > target)  // 剪枝,部分和已经大于target,无需向下搜索
		{
			sum -= a;
			continue;
		}
		p = p * 10 + i;  // 记录划分方式

		char b[7];   // 构造n的后i位字符序列,继续递归
		int j = 0;
		for(int k = i; k < len; k++)
		{
			b[j++] = s[k];
		}
		b[j] = '\0';

		dfs(b, len - i);

		sum -= a;  回溯
		p /= 10;
	}
	return;
}

int main()
{
	char s[7];
	while(cin >> target >> s)
	{
		int len = strlen(s);
		int n = getvalue(s, len);

		if(!target && !n)  // 边界条件
			break;

		if(target == n)  // 目标值与打印纸上的数字一致
		{
			cout << target << " " << n << endl;
			continue;
		}

		int num = n;  // 定义临时变量
		int k = 0;   // n的各位数字之和
		while(num)
		{
			k += num % 10;  // 逐位划分是和的最小划分方式
			num /= 10;
		}
		if(k > target)  // 
		{
			cout << "error" << endl;
			continue;
		}

		// Initial
		result = -1;
		sum = 0;
		path = 0;
		p = 0;
		memset(visit, 0, sizeof(visit));


		// DFS
		dfs(s, len);

		// output
		if(visit[result] > 1)
			cout << "rejected" << endl;
		else if(visit[result] == 1)
		{
			cout << result << " ";

			int l = getlen(path);
			for(int i = 1; i <= l; i++)
			{
				int k = gethead(path, 1);
				cout << gethead(n, k) << " ";
				n = gettail(n, len -= k);
				path = gettail(path, l - i);
			}
			cout << endl;
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator