题意：给n个数a[i], 要求b[i]每位数的和等于a[i], 并且b[i]要严格递增 求最小的b[i]
b[0]最小一定是X9999...这样的形式
后面的b[i]位数一定大于等于前一个
用ans[i][0]记录b[i]的位数
也就是 每次从ans[i-0][0]位开始 若不满足b[i]>b[i-1] 则位数加1
位数加1之后 必定满足b[i]>b[i-1] 则之后只需用递归遍历各位即可
1 int a[305]; 2 int ans[305][1005]; 3 bool dfs(int i, int num, int sum, bool f) 4 { 5 // printf("********** %d %d %d %d ********** ", i, num, sum, f); 6 if(!num) 7 return f; 8 for(int j=(f? (num==ans[i][0]? 1:0):ans[i-1][num]);j<=9;j++) 9 if(j+9*(num-1)>=sum && sum>=j && dfs(i, num-1, sum-j, f || j>ans[i-1][num])) 10 { 11 ans[i][num]=j; 12 return true; 13 } 14 return false; 15 } 16 int main() 17 { 18 int n; 19 while(~scanf("%d", &n)) 20 { 21 for(int i=1;i<=n;i++) 22 scanf("%d", &a[i]); 23 memset(ans, 0, sizeof(ans)); 24 while(a[1]>9) 25 a[1]-=9, ans[1][++ans[1][0]]=9; 26 ans[1][++ans[1][0]]=a[1]; 27 for(int i=ans[1][0];i>0;i--) 28 printf("%d", ans[1][i]); 29 printf(" "); 30 for(int i=2;i<=n;i++) 31 { 32 ans[i][0]=ans[i-1][0]; 33 while(ans[i][0]*9<a[i]) 34 ans[i][0]++; 35 if(!dfs(i, ans[i][0], a[i], ans[i][0]>ans[i-1][0])) 36 { 37 ans[i][0]++; 38 dfs(i, ans[i][0], a[i], true); 39 } 40 for(int j=ans[i][0];j>0;j--) 41 printf("%d", ans[i][j]); 42 printf(" "); 43 } 44 } 45 return 0; 46 }