URAL 1658 Sum of Digits

URAL 1658

思路：

dp+记录路径

状态：dp[i][j]表示s1为i,s2为j的最小位数

初始状态：dp[0][0]=0

状态转移：dp[i][j]=min(dp[i-k][j-k*k]+1,dp[i][j])(0<=k<10)

在状态转移时用一个数组v[i][j]记录选的k

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))

const int INF=0x3f3f3f3f;
int dp[905][8105];
int v[905][8105];
vector<int>ans;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    mem(dp,INF);
    dp[0][0]=0;
    for(int i=0;i<=900;i++){
        for(int j=0;j<=8100;j++){
            for(int k=0;k<=9;k++){
                if(i-k>=0&&j-k*k>=0){
                    if(dp[i-k][j-k*k]+1<dp[i][j]){
                        dp[i][j]=dp[i-k][j-k*k]+1;
                        v[i][j]=k;
                    }
                }
            }
        }
    }
    int T,s1,s2;
    cin>>T;
    while(T--){
        cin>>s1>>s2;
        if(s1>900||s2>8100||dp[s1][s2]>100){
            cout<<"No solution"<<endl;
            continue;
        }
        ans.clear();
        while(true){
            if(s1==0&&s2==0)break;
            ans.pb(v[s1][s2]);
            int t=v[s1][s2];
            s1-=t;
            s2-=t*t;
        }
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++)cout<<ans[i];
        cout<<endl;
    }
    return 0;
}