1682.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 1682 on 2006-09-14 at 16:08:23 */
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
 
const int N = 9, SN = 1 << N;
const int INF = 1 << 20;
 
int len[SN], prev[SN], v[SN], ledz[SN], n;
char num[N+1];
map<int, int> dic;
 
int find(int);
 
int main()
{
	while(gets(num)[0] != '0') {
		n = strlen(num); dic.clear();
		memset(len, -1, sizeof(len)); memset(prev, -1, sizeof(prev));
		for(int i = 1; i < (1<<n); i++) {
			ledz[i] = 0;
			for(int j = v[i] = 0; j < n; j++) {
				if(!(i&(1<<j))) continue;
				v[i] = v[i]*10+num[j]-'0';
				if(v[i] == 0) ledz[i]++;
			}
			if(ledz[i] == 1 && v[i] == 0) ledz[i] = 0;
			if(!ledz[i] && !dic.count(v[i])) dic[v[i]] = i;
		}
		find((1<<n)-1);
		for(int now = (1<<n)-1; now > 0; now = prev[now]) {
			for(int i = 0; i < n; i++)
				if(now&(1<<i)) putchar(num[i]);
			putchar(prev[now] == -1 ? '\n' : ' ');
		}
	}
 
	return 0;
}
 
int find(int st)
{
	if(st == 0) return -INF;
	else if(v[st] == 0) { return 0; }
	if(len[st] == -1) {
		len[st] = 0;
		for(int i = 1; i < st; i++) {
			if((st|i) != st || ledz[i] || v[i] <= 1 || v[st]%v[i] != 0) continue;
			int rem = dic.find(v[st^i])->second, nxt = find(rem)+1;
			if(prev[st] == -1 || nxt > len[st] || (nxt == len[st] && v[rem] < v[prev[st]]))
				{ prev[st] = rem; len[st] = nxt; }
		}
	}
	return len[st];
}