hdu 3022 Sum of Digits

http://acm.hdu.edu.cn/showproblem.php?pid=3022

题意：

最多不超过10000组数据，每组数据给定两个数n,m，求一个最小的数，使得该数每一位之和等于n，每一位的平方和等于m。

若无解或者答案超过100位，输出no solution。

 

n最大=900，m最大=8100

dp[i][j]表示和为i，平方和为j的最少位数

dp2[i][j]表示和为i，平方和为j的最小首位数

竟然一直在思考有前导0怎么办，最优解肯定不能出现0啊啊啊

 

#include<cstdio>

#include<algorithm>

using namespace std;

#define N 901

#define M 8101

int dp[N][M],dp2[N][M];

void pre()

{

    for(int i=;i<=;++i) dp[i][i*i]=,dp2[i][i*i]=i;

    for(int i=;i<N;++i)

        for(int j=;j<M;++j)

            if(dp[i][j] && dp[i][j]!=)

                for(int k=;k<=;++k)

                    if(!dp[i+k][j+k*k] || dp[i+k][j+k*k]>dp[i][j]+)

                    {

                        dp[i+k][j+k*k]=dp[i][j]+;

                        dp2[i+k][j+k*k]=k;

                    }

                    else if(dp[i+k][j+k*k]==dp[i][j]+) dp2[i+k][j+k*k]=min(dp2[i+k][j+k*k],k);

}

int main()

{

    pre();

    int T,n,m,d;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        if(n>=N || m>=M || !dp[n][m]) printf("No solution\n");

        else

        {

            while(n)

            {

                printf("%d",d=dp2[n][m]);

                n-=d;

                m-=d*d;

            }

            putchar('\n');

        }

    }

    return ;

}