哥為了來年交過好運，大年三十特地上來刷這題，結果就蛋疼到了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