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 13110403047 at 2014-11-27 15:07:17 on Problem 1416
在更新最优解的时候用另外一个数组更新路径就好了。。
代码很挫。。sad
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include<time.h>
#include <stack>
#include <map>
#include <set>
#define maxn 360
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define pp pair<int,int>
#define ull unsigned long long
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
char s[100];
int ok,ans,path[20],ans_path[20],len,goal,rej,ans_tot;
int my_pow(int a,int n)
{
	int p=1;
	for(int i=1;i<=n;i++)
		p*=a;
	return p;
}
void dfs(int num,int sum,int tot)
{
	if(sum>goal)return ;
	if(num>=len)
	{
		if(sum>ans&&sum<=goal)
		{
			memcpy(ans_path,path,sizeof(int)*tot);
			ok=1;rej=1;ans=sum;ans_tot=tot;
			return ;
		}
		else if(sum==ans&&sum<=goal)
		{
			rej++;
			return ;
		}
		return ;
	}
	for(int i=1;num+i<=len;i++)
	{
		int j=num+i,tem=0,sb=0;
		while(j>num)tem+=(s[j--]-'0')*my_pow(10,sb++);
		path[tot]=num+i;
		dfs(num+i,sum+tem,tot+1);
		path[tot]=-1;
	}
}
void print()
{
	if(rej>1)
	{
		puts("rejected");
		return ;
	}
	if(ok)
	{
		printf("%d",ans);
		for(int i=0;i<ans_tot;i++)
		{
			printf(" ");
			for(int j=(i!=0?ans_path[i-1]+1:1);j<=ans_path[i];j++)
			printf("%c",s[j]);
		}
		puts("");
	}
	else
	puts("error");
}
int main()
{
	while(scanf("%d%s",&goal,s+1)&&(goal!=0&&s[1]!='0'))
	{
		memset(path,-1,sizeof(path));
		s[0]=2;len=strlen(s)-1;
		ans=-INF;ok=0;rej=0;dfs(0,0,0);
		print();
	}
	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