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

AC了,贡献了一次WA,把rejected写成reject了。DFS,贴代码

Posted by moment1 at 2009-05-31 16:10:32 on Problem 1416
/**
  * DFS:由于在遍历时,preTemp会随时变化,因此当找到当前最优解时需要用preBest来保存preTemp
  */
#include <iostream>
#include <cmath>
#define MAX_LEN 6
using namespace std;

int preTemp[MAX_LEN + 1];
int preBest[MAX_LEN + 1];
int dis[MAX_LEN + 1];
int upper, input;
int len;
int total;
int resType;
void init()
{
	int temp = input;
	//计算输入数据长度
	len = 1;
	while((temp = temp / 10) != 0)
		len ++;
	memset(preTemp, 0, sizeof(preTemp));
	memset(preBest, 0, sizeof(preBest));
	memset(dis, 0, sizeof(dis));
	resType = 0;
	total = 0;
}
//计算从start开始,长度为dlen的数据的大小,例如对于12345, get(2, 3)返回234
int get(int start, int dlen)
{
	int temp = input, i;
	int s1 = pow((double)10, len - 1);
	for(i = 1; i < start; i++)
	{
		temp = temp % s1;
		s1 = s1 / 10;
	}
	for(i = 1; i <= len - start + 1 - dlen; i++)
		temp = temp / 10;
	return temp;
}


void solve(int curPos)
{
	//出口条件,超出位数
	if(curPos > len)
	{
		//已经超出上限,不用考虑
		if(dis[curPos - 1] > upper)
			return;
		//得到当前最优解
		if(dis[curPos - 1] > total)
		{
			resType = 2;
			total = dis[curPos - 1];
			//保存分割路径
			for(int i = 1; i <= MAX_LEN; i++)
				preBest[i] = preTemp[i];
		}
		//找到的当前最优解与之前的有重复
		else if(dis[curPos - 1] == total && total > 0)
			resType = 1;
		return;
	}
	int dlen = 0, curVal = 0;
	//从当前位置向后遍历,逐渐增加当前值的长度
	for(dlen = 1; dlen <= len - curPos + 1; dlen++)
	{
		//得到当前值
		curVal = get(curPos, dlen);
		//标记临时路径分割前驱
		preTemp[curPos + dlen - 1] = curPos; 
		//标记最优值大小
		dis[curPos + dlen - 1] = dis[curPos - 1] + curVal;
		//从下一位开始DFS
		solve(curPos + dlen);
		//需要状态还原
		preTemp[curPos + dlen - 1] = 0; 
		dis[curPos + dlen - 1] = 0;
	}
}
//递归打印路径
void printt(int curPos)
{
	int prePos;
	if(curPos == 0)
		return;
	prePos = preBest[curPos];
	printt(prePos - 1);
	cout<<" ";
	cout<<get(prePos, curPos - prePos + 1);
	
}
//打印结果
void showRes()
{
	if(resType == 0)
		cout<<"error"<<endl;
	else if(resType == 1)
		cout<<"rejected"<<endl;
	else
	{
		cout<<total;
		printt(len);
		cout<<endl;
	}
}
int main()
{
	while(cin>>upper>>input && (upper != 0 || input != 0))
	{
		init();
		solve(1);
		showRes();
	}
	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