首页 > 代码库 > poj1416

poj1416

#include<iostream>
using namespace std;

int target,datanum;
int road[100],temproad[100];
int N,flag,maxsum;
int data[100],datatemp[100];
int tail;

void cun(int n)
{
    tail=0;
    
    while(n/10)
    {
        int m=n%10;
        n=n/10;
        datatemp[tail++]=m;
    }
    datatemp[tail++]=n%10;
    for(int i=0;i<tail;i++)
        data[i]=datatemp[tail-i-1];
    return;
}

void dfs(int n, int step, int sum, int tobe)
{
    if(sum>target)
        return;

    if(n==N-1)
    {
        sum=sum+tobe*10+data[N-1];
        temproad[step]=tobe*10+data[N-1];
        if(sum>target)
            return;
        if(sum==maxsum)
            flag=1;
        else if(sum>maxsum)
        {
            for(int i=0;i<100;i++)
                road[i]=-1;
            flag=0;
            maxsum=sum;
            for(int i=0;i<=step;i++)
                road[i]=temproad[i];
        }
        return;
    }

    temproad[step]=tobe*10+data[n];
    dfs(n+1,step+1,sum+tobe*10+data[n],0);//
    temproad[step]=-1;

    dfs(n+1,step,sum,tobe*10+data[n]);
}

int main()
{
    //freopen("input.txt","r",stdin);
    while(1)
    {
        cin>>target>>datanum;
        //cout<<target<<alldata<<endl;
        if(target==0&&datanum==0)
            break;
        if(target==datanum)
        {
            cout<<target<< <<target<<endl;
            continue;
        }
        for(int i=0;i<100;i++)
            data[i]=-1;
        cun(datanum);
        N=tail;
    
        maxsum=-1;
        flag=0;
        for(int i=0;i<100;i++)
        {
            road[i]=-1;
            temproad[i]=-1;
        }
        dfs(0,0,0,0);
        if(maxsum==-1)
            cout<<"error"<<endl;
        else if(flag==1)
            cout<<"rejected"<<endl;
        else
        {
            cout<<maxsum<< ;
            for(int i=0;i<100;i++)
            {
                if(road[i]!=-1)
                    cout<<road[i]<< ;
            }
             cout<<endl;
        }
    }
    return 0;
}

 

poj1416