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=1;i<=9;++i) dp[i][i*i]=1,dp2[i][i*i]=i; for(int i=1;i<N;++i) for(int j=1;j<M;++j) if(dp[i][j] && dp[i][j]!=100) for(int k=1;k<=9;++k) if(!dp[i+k][j+k*k] || dp[i+k][j+k*k]>dp[i][j]+1) { dp[i+k][j+k*k]=dp[i][j]+1; dp2[i+k][j+k*k]=k; } else if(dp[i+k][j+k*k]==dp[i][j]+1) 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 0; }