URAL 1658. Sum of Digits(DP)

题目链接

隔了一年零三个月,重新刷URAL,这题挺麻烦的输出路径。输出路径挺扯的,乱写了写乱改改就A了。。。我本来想用很靠谱,记录每一条路径的,然后输出最小的,结果Tle,然后我使劲水水又过了一组,发现别人的题解。。直接来了一次 就过了。。我乱搞了搞,倒着记录最小的,然后倒着输出,就过了。。。

 #include <cstring>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF 10000000
int dp[][];
int pre[][];
int s[];
struct node
{
int a,b;
};
void spfa()
{
int i,a,b;
queue<node> que;
node temp,u,v;
for(i = ; i < ; i ++)
{
temp.a = i;
temp.b = i*i;
dp[i][i*i] = ;
pre[i][i*i] = i;
que.push(temp);
}
while(!que.empty())
{
u = que.front();
a = u.a;
b = u.b;
que.pop();
if(a > ) continue;
if(b > ) continue;
for(i = ; i < ; i ++)
{
v.a = i+a;
v.b = i*i+b;
if(i + a > ) continue;
if(i*i + b > ) continue;
if(dp[v.a][v.b] > dp[u.a][u.b] + )
{
pre[v.a][v.b] = i;
dp[v.a][v.b] = dp[u.a][u.b] + ;
que.push(v);
}
}
}
return ;
} int main()
{
int t,n,m,i,j;
int top;
for(i = ; i <= ; i ++)
{
for(j = ; j <= ; j ++)
{
dp[i][j] = INF;
pre[i][j] = INF;
}
}
spfa();
scanf("%d",&t);
top = ;
while(t--)
{
scanf("%d%d",&n,&m);
if(n > ||m > )
{
printf("No solution\n");
continue;
}
else if(dp[n][m] > )
{
printf("No solution\n");
continue;
}
int top = ;
while(n&&m)
{
i = pre[n][m];
s[top++] = i;
n = n - i;
m = m - i*i;
}
for(i = top-;i >= ;i --)
printf("%d",s[i]);
printf("\n");
}
return ;
}
上一篇:error:cv_bridge---opencv和ros连接起来的桥


下一篇:Java学习_int和Integer的区别+包装类