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

挤进了前2000,1997留念,留念!附上源码

Posted by vjubge4 at 2019-05-09 14:35:40 on Problem 1416
#include<cstdio>
#include<cstring>
#include<algorithm>
#pragma warning(disable: 4996)
using namespace std;
typedef pair<int, int> P;
int N, M;
int Len;
char s[12];
int pw[] = { 1, 10, 100, 1000, 10000, 100000, 1000000 };
int get_num(int from, int to) {
	if (to == from) {
		return 0;
	}
	int t = M;
	t /= pw[from];
	t %= pw[to - from];
	return t;
}
P Path[12][12];
int res;
P res_p;
bool uni;

bool dfs(int n_cut, int cur_cut, int cur_to, int cur_form, int cur_num) {
	if (cur_cut == n_cut) {
		if (cur_num <= N && cur_to == Len) {
			if (cur_num > res) {
				res = cur_num;
				uni = true;
				Path[cur_form][cur_to].first = -1;
				Path[cur_form][cur_to].second = -1;
				return true;
			} else if (cur_num == res) {
				uni = false;
				return false;
			}
		}
		return false;
	}
	if (cur_num > N) {
		return false;
	}
	bool flag = false;
	for (int i = cur_to + 1; i <= Len; i++) {
		int num = get_num(cur_to, i);
		if (num != -1) {
			if (dfs(n_cut, cur_cut + 1, i, cur_to, num + cur_num)) {
				Path[cur_form][cur_to].first = cur_to;
				Path[cur_form][cur_to].second = i;
				flag = true;
			}
		}
	}
	return flag;
}

void print(P p) {
	p = Path[p.first][p.second];
	if (p.first != -1 && p.second != -1) {
		print(p);
		printf("%d ", get_num(p.first, p.second));
	}
}

int main() {
	while (~scanf("%d %s", &N, s)) {
		if (N == 0 && s[0] == '0') {
			break;
		}
		Len = strlen(s);
		M = atoi(s);
		res = -1;
		uni = false;
		for (int i = 1; i <= Len; i++) {
			dfs(i, 0, 0, 0, 0);
		}
		if (res == -1) {
			printf("error\n");
			continue;
		}
		if (!uni) {
			printf("rejected \n");
			continue;
		}
		printf("%d ", res);
		print(res_p);
		printf("\n");
	}
}

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