zoj2170.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <stdio.h>
#include <set>

using namespace std;

struct elem
{
	int num,d;
	int a[11];
};

bool operator<(const elem &a,const elem &b)
{
	return a.num<b.num;
}

elem sts[2000];

int n,a[100],m,an;
set<int> dict;

bool input()
{
	scanf("%d",&n);
	if (n==0) return 0;
	an=0;
	int num=n;
	while (num)
	{
		a[an++]=num%10;
		num/=10;
	}
	dict.clear();
	return 1;
}

void dfs(const int &td,const int &num,const int &len)
{
	if (td==0)
	{
		if (len) dict.insert(num);
		return;
	}
	dfs(td-1,num,len);
	dfs(td-1,num*10+a[td-1],len+1);
}

int cnts(int num)
{
	int ans=0;
	while (num)
	{
		++ans;
		num/=10;
	}
	return ans>1?ans:1;
}

void init()
{
	set<int>::iterator iter;
	m=0;
	int i,tmp;
	for (iter=dict.begin();iter!=dict.end();++iter)
	{
		sts[m].num=*iter;
		sts[m].d=cnts(*iter);
		tmp=sts[m].num;
		for (i=0;i<sts[m].d;++i)
		{
			sts[m].a[i]=tmp%10;
			tmp/=10;
		}
		++m;
	}
}

int dps[2000],dpb[2000];

bool judge(const int &anum,int a[],const int &al,int b[],const int &bl)
{
//	if (anum==8013824)
//	{
//		printf("!!");
//		for (int i=0;i<bl;++i)
//			printf("%d",b[bl-i-1]);
//		printf("\n");
//	}
	int c=0,i=0,j=0,t=1;
	while (i<al&&j<bl)
	{
		if (a[i]==b[j])
		{
			++i;
			++j;
		}
		else
		{
			if (c!=0&&a[i]==0) return 0;
			c+=a[i]*t;
			if (a[i]||c) t*=10;
			++i;
		}
	}
	if (j<bl) return 0;
	while (i<al)
	{
		if (c!=0&&a[i]==0) return 0;
		c+=a[i]*t;
		if (a[i]||c) t*=10;
		++i;
	}
	//printf("!!%d\n",c);
	return c!=0&&c!=1&&anum%c==0;
}

void dp()
{
	int i,j;
	for (i=0;i<m;++i)
	{
		dps[i]=0;
		dpb[i]=-1;
		for (j=0;j<i;++j)
			if (sts[i].d>sts[j].d&&judge(sts[i].num,sts[i].a,sts[i].d,sts[j].a,sts[j].d)&&dps[i]<dps[j]+1)
			{
				dps[i]=dps[j]+1;
				dpb[i]=j;
			}
	}
//	for (i=0;i<m;++i)
//		printf("##%d %d\n",sts[i].num,dps[i]);
}

void output()
{
	int num=m-1;
	while (num>-1)
	{
		if (num!=m-1) printf(" ");
		printf("%d",sts[num].num);
		num=dpb[num];
	}
	printf("\n");
}

int main()
{
	while (input())
	{
		dfs(an,0,0);
		init();
		dp();
		output();
	}
	return 0;
}