题目地址：HDUOJ：Problem – 3022、Timus Online Judge：1658. Sum of Digits @ Timus Online Judge

题目描述

Petka thought of a positive integer n and reported to Chapaev the sum of its digits and the sum of its squared digits. Chapaev scratched his head and said: “Well, Petka, I won’t find just your number, but I can find the smallest fitting number.” Can you do the same?
给定一个数字每位上数字的和和平方和，求符合条件的最小数字。

输入输出格式

输入格式：
The first line contains the number of test cases t (no more than 10000). In each of the following t lines there are numbers s1 and s2 (1 ≤ s1, s2 ≤ 10000) separated by a space. They are the sum of digits and the sum of squared digits of the number n.

输出格式：
For each test case, output in a separate line the smallest fitting number n, or “No solution” if there is no such number or if it contains more than 100 digits.

输入输出样例

输入样例#1：

4
9 81
12 9
6 10
7 9

输出样例#1：

9
No solution
1122
111112

题解

是一个很巧妙的DP。
首先s1≤900，s2≤8100是很好确定的。大于的情况直接无解。
首先，考虑两个DP，f[i][j]代表和为i平方和为j的数字最小长度，g[i][j]代表和为i平方和为j的最小开头数字。容易知道最优解数字中肯定不含0。
我们枚举i和j，然后从小到大枚举扩展长度的数字k，如果在f[i][j]的基础上加入k后长度比f[i+k][j+k*k]更小，那么应当更新答案，此时k也就是g[i][j]的值。如果加入k后与f[i+k][j+k*k]长度一样，那么g[i][j]看一下是否比k大，更新g[i][j]答案。这是一个很暴力的转移。
上面的两个DP数组可以预处理出来，查询的时候先看是否可行，是否超100，然后每次用g[i][j]输出，s1-=g[i][j]，s2-=g[i][j]*g[i][j]，直到s1或s2为0。

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN1 = 910, MAXN2 = 8110;

int T, s1, s2, f[MAXN1][MAXN2], g[MAXN1][MAXN2];

inline int sqr(int x) {
    return x * x;
}

inline void init() {
    for(int i = 1; i <= 9; i++) {
        f[i][sqr(i)] = 1;
        g[i][sqr(i)] = i;
    }
    for(int i = 1; i <= 900; i++) {
        for(int j = 1; j <= 8100; j++) {
            if(f[i][j]) {
                for(int k = 1; k <= 9; k++) {
                    if(!f[i + k][j + sqr(k)] || f[i + k][j + sqr(k)] > f[i][j] + 1) {
                        f[i + k][j + sqr(k)] = f[i][j] + 1;
                        g[i + k][j + sqr(k)] = k;
                    } else if(f[i + k][j + sqr(k)] == f[i][j] + 1) {
                        g[i + k][j + sqr(k)] = std::min(g[i + k][j + sqr(k)] = k, k);
                    }
                }
            }
        }
    }
}

int main() {
    T = readint();
    init();
    while(T--) {
        s1 = readint();
        s2 = readint();
        if(s1 > 900 || s2 > 8100 || !f[s1][s2] || f[s1][s2] > 100) {
            printf("No solution\n");
            continue;
        }
        while(s1 && s2) {
            int t = g[s1][s2];
            printf("%d", t);
            s1 -= t;
            s2 -= sqr(t);
        }
        printf("\n");
    }
    return 0;
}