哥为了来年交过好运，大年三十特地上来刷这题，结果就蛋疼到了11：50才写完，不过很高兴能够1A，希望今年事事顺利！
题目要求对一个给定的自然数，求出一个符合规定的的降序列，这个规则就是每次从数列前一项减去几个数位，而这几个数位构成的“合法自然数”必须又恰好是该项的约数。注意到单调减的特性，很容易想到记忆化，但是数据范围十亿以内，不能直接存表。注意到每一个合法的约数都是该数的“子序列”，因此可以把数位的使用状态使用二进制子集表示，于是可以把数组规模压缩到 1<<9。
剩余的就是比较繁琐的细节，特别要注意一个合法的Subfactor 必须是一个自然数，大于1小于该项本身，并且不能是多重0或前导0。
1
#include<cstdio>
2#include<cstring>
3int dp[1<<10][2];
4int n;
5
6
int makeNum(unsigned long cnt)
{
7
char str1[11],str2[11];
8 int len1,len2=0;
9 int inter;
10 len1=sprintf(str1,"%d",n);
11 for(int i=len1-1;i>-1;--i)
12 if(cnt&(1<<i))
13 str2[len2++]=str1[len1-1-i];
14 str2[len2]='\0'; sscanf(str2,"%d",&inter);
15 if(inter==0||str2[0]!='0') return inter;
16 else return -1; // 非法前导0
17
}
18
19unsigned long clear(unsigned long cnt){
20 char str[11];
21 bool have;
22 unsigned long l=1;
23 int i,len=sprintf(str,"%d",n);
24
if( makeNum(cnt)!=0 ){ // 去前导0
25 for(have=i=0;i<len&&(have==false);i++){
26 if(str[i]!='0'&& ((cnt>>len-1-i)&l) ) have=true;
27 if(str[i]=='0'&& ((cnt>>len-1-i)&l) ) cnt=cnt&(~(l<<len-1-i));
28
}
29 }else{ // 排除 "0000 "
30 for(have=i=0;i<len;i++)
31 if(!have&& ((cnt>>len-1-i)&l) ) have=true;
32 else
33 if( have&& ((cnt>>len-1-i)&l) ) cnt=cnt&(~(l<<len-1-i));
34 }
35 return cnt;
36}
37
38int dfs(unsigned long s,int *next){
39 int len,cnt1,cnt2;
40 if(dp[s][0]==0){
41 cnt1=makeNum(s);
42 for(unsigned long i=0; ;i=(i-s) & s){
43 if(i==s) break;
44 if(i!=0){
45 if( (cnt2=makeNum(i))>1 && cnt1%cnt2==0 ){
46 len=dfs(clear(s&(~i)),next); // 和谐~
47 if( dp[s][0]<len ||
48 (dp[s][0]==len && makeNum(dp[s][1])>makeNum(*next)) ){
49
50 dp[s][0]=len;
51 dp[s][1]=*next;
52 }
53 }
54 }
55 }
56 ++dp[s][0];
57 }
58 *next=s;
59 return dp[s][0];
60}
61
62int main(){
63 char str[11];
64 int k,i,next;
65 unsigned long s;
66 while(scanf("%d",&n),n){
67 for(i=0;i<(1<<9);++i){ dp[i][0]=0; dp[i][1]=-1; }
68 k=sprintf(str,"%d",n);
69 for(s=1,i=1;i<k;i++){ s<<=1; s|=1; }
70 dfs(s,&next); // dp
71 printf("%d",makeNum(s)); next=dp[s][1];
72 while(next!=-1){
73 printf(" %d",makeNum(next));
74 next=dp[next][1];
75 }printf("\n");
76 }
77 return 0;
78}
79