Sum of Digits
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 149 Accepted Submission(s): 46
Problem Description
Petka thought of a positive integer n and reported to Chapayev the sum of its digits and the sum of its squared digits. Chapayev 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?
Input
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.
Output
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.
Sample Input
Sample Output
9
No solution
1122
111112
Source
Recommend
gaojie
根據output的提示，結果不可能大于100位，我們可以猜出，s1最大就是900，s2最大是8100，所以，完全可以(s1 * s2)的復雜度。
dp[i][j] = min(dp[i - k][j - k * k] + 1, dp[i][j])，其中i表示和，j表示平方和是，k表示多出最高位是k，dp數組記錄位數，同時開一個d數組記錄可行方案的首位。
根據貪心思想，讓結果最小，所以先盡量求出最小的位數，之后根據位數構造最小的數。得出最小位數后，可以遞歸求出答案（d數組記錄的是可行方案的首位，所以遞歸很好實現。）
代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int dp[901][8101], d[901][8101];
int T, n, m;
int main()
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= 9; ++i)
{
dp[i][i * i] = 1;
d[i][i * i] = i;
}
for (int i = 1; i <= 900; ++i)
{
for (int j = i; j <= 8100; ++j)
{
for (int k = 1; k <= 9; ++k)
{
if (i < k || j < k * k) break;
if (dp[i - k][j - k * k] == 0 || dp[i - k][j - k * k] == 100) continue;
if (dp[i][j] == 0 || dp[i - k][j - k * k] + 1 < dp[i][j])
{
dp[i][j] = dp[i - k][j - k * k] + 1;
d[i][j] = k;
}
}
}
}
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
if (n > 900 || m > 8100 || dp[n][m] == 0)
{
printf("No solution\n");
continue;
}
while (dp[n][m])
{
int dig = d[n][m];
printf("%d", dig);
n -= dig;
m -= dig * dig;
}
printf("\n");
}
return 0;
}
posted on 2011-10-15 22:14
LLawliet 閱讀(218)
評論(0) 編輯 收藏 引用 所屬分類:
動態規劃