这题卡了挺久了 昨天试着用类似dfs的方法直接TLE在第二组 看了下题解，，发现s1,s2的范围是个幌子。。100位最大的s1900 s28100 觉得s1s2太大不敢开二维。。
这样就简单了 类似背包 dp[s1][s2]表示组成s2s2最少的位数 其实就是装进去多少个数字 正好把s1s2装满
把DP部分预处理之后放在外面 不然会超时
#include <iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define INF 0xfffffff
int s1,s2;
int dp[][];
int path[],flag;
void dfs(int ss1,int ss2,int u,int v)
{
path[u] = v;
if(flag) return ;
int i;
if(u==&&ss1==&&ss2==)
{
flag = ;
for(i = dp[s1][s2] ; i>=; i--)
printf("%d",path[i]);
puts("");
return ;
}
if(ss1<=||ss2<=)
return ;
u--;
for(i = ; i <= ; i++)
{
if(ss1-i<||ss2-i*i<)
continue;
if(dp[ss1-i][ss2-i*i]+==dp[ss1][ss2])
dfs(ss1-i,ss2-i*i,u,i);
if(flag) break;
}
}
int main()
{
int i,j,g,t;
scanf("%d",&t);
for(i = ; i <= ; i++)
for(j = ; j <= ; j++)
dp[i][j] = INF;
dp[][] = ;
for(i = ; i <= ; i++)
for(j = i ; j <= ; j++)
for(g = i*i ; g <= ; g++)
dp[j][g] = min(dp[j][g],dp[j-i][g-i*i]+);
while(t--)
{
scanf("%d%d",&s1,&s2);
if(s1>||s2>)
{
printf("No solution\n");
continue;
}
flag = ;
if(dp[s1][s2]==INF||dp[s1][s2]>)
{
printf("No solution\n");
}
else
{
for(i =; i <= ; i++)
{
if(s1-i<||s2-i*i<)
continue;
if(dp[s1-i][s2-i*i]+==dp[s1][s2])
dfs(s1-i,s2-i*i,dp[s1][s2],i);
if(flag) break;
}
}
}
return ;
}