【UVA – 1583】Digit Generator【紫书】【dfs】

【UVA – 1583】Digit Generator【紫书】

题目链接:https://vjudge.net/problem/UVA-1583

udebug数据链接:https://www.udebug.com/UVa/1583

Solution:

#include <iostream>

using namespace std;

const int LIM = 1e5;
int table[LIM + 1];

void dfs(int crt, int num) {
    int sum = crt + num;
    if (sum > LIM) return;
    if (!table[sum]) table[sum] = num;
    else if (num < table[sum]) table[sum] = num;
    for (int i = num ? 0 : 1; i <= 9; i++)
        dfs(crt + i, num * 10 + i);
}

inline void build() { dfs(0, 0); }

int main(void) {
    build();
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("%d\n", table[n]);
    }
    return 0;
}

 

相关阅读:

《算法竞赛入门经典》(紫书)全AC代码