做完这个题就一个感觉――智商捉鸡。
虽然题目中的 1 <= s1,s2 <= 10000,但是解决方案不能超出100位，也就是说 1 <= s1 <= 900 && 1<= s2 <= 8100。
好了，发现这个坑开不出数组的问题就解决了。然后试着用BFS来解决，没想到会TLE，感觉节点也不是很多唉。
然后感觉像是二维背包，dp[ i ][ j ] = min(dp[ i-x ][j - x*x]+1), 1 <= x <= 9。dp[ i ][ j ]记录到达这种状态时的最小位数。
然后继续TLE，然后试着写成记忆化搜索的样子，试着剪枝。然后写错了，这里要特别提一下，就是当一种子状态的
最优解确定后要保证不在虽后续状态的变化而变化，也就是所谓的无后效性。然后真的没辙了，去翻了一下博客。。。。
表示预处理打表这项基本的生存技能已经废弃很久了。 。 。
#include#include #include #include #include #include #include #include #pragma comment(linker, "/STACK:1024000000"); #define LL long long int #define ULL unsigned long long int #define _LL __int64 #define _INF 0x3f3f3f3f #define INF 1000000 #define Mod 1000000009 using namespace std; int dp[901][8101]; int a[10]; int num[910]; int Top; void Output(int l,int r) { if(l == 0 && r == 0) return ; for(int i = 1;i <= 9; ++i) { if(dp[l-i][r-a[i]] == dp[l][r]-1) { num[Top++] = i; Output(l-i,r-a[i]); return ; } } } int main() { int l,r; int t,i,j,k; for(i = 1;i <= 9; ++i) a[i] = i*i; memset(dp,INF,sizeof(dp)); dp[0][0] = 0; for(i = 1;i <= 9; ++i) { for(j = i;j <= 900; ++j) { for(k = a[i];k <= 8100; ++k) { dp[j][k] = min(dp[j][k],dp[j-i][k-a[i]]+1); } } } scanf("%d",&t); while(t--) { scanf("%d %d",&l,&r); if(l > r || l > 900 || r > 8100) { printf("No solution\n"); } else { if(dp[l][r] == -1 || dp[l][r] > 100) { printf("No solution\n"); } else { Top = 0; Output(l,r); sort(num,num+Top); for(i = 0;i < Top; ++i) { printf("%d",num[i]); } printf("\n"); } } } return 0; }