首页 > 代码库 > DFS/POJ 1416 Shredding Company

DFS/POJ 1416 Shredding Company

 1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 int mmax,sum; 5 char s[10]; 6 bool v[10],way[10]; 7 bool rejected; 8 void dfs(int dep,int value,int before) 9 {10     int now=0;11     for (int i=before;i<dep;i++)12     {13         now=now*10;14         now=now+s[i]-0;15     }16     if (dep==strlen(s))17     {18         int ans=value+now;19         if (ans>mmax) return;20         if (ans==sum)21         {22             rejected=true;23             return;24         }25         else if (ans>sum)26         {27             sum=ans;28             rejected=false;29             for (int i=0;i<strlen(s);i++) way[i]=v[i];30             return;31         }32         return;33     }34     if (value>mmax) return;35     v[dep]=1;36     dfs(dep+1,value+now,dep);37     v[dep]=0;38     dfs(dep+1,value,before);39 40 }41 int main()42 {43     scanf("%d%s",&mmax,s);44     while (mmax!=0)45     {46         memset(v,0,sizeof(v));47         sum=0;48         v[0]=1;49         rejected=false;50         dfs(1,0,0);51         if (rejected==true) printf("rejected\n");52         else if (sum==0) printf("error\n");53         else54         {55             printf("%d",sum);56             for (int i=0;i<strlen(s);i++)57             {58                 if (way[i]==1) printf(" ");59                 printf("%c",s[i]);60             }61             printf("\n");62         }63         scanf("%d%s",&mmax,s);64     }65     return 0;66 }

 

DFS/POJ 1416 Shredding Company