Shredding Company (pku 1416)

作者在 2007-12-29 23:40:40 发布以下内容

其实是没什么难度的题,但是自己写错了一个字母,一直wa了下午都不知道是怎么回事,晚上才看到,郁闷啊~~~

题目是一个深搜,做不做优化都可以但是本着优秀代码的原则还是应该修枝一下下的,不过不要像我一样,自以为自己在深搜之前比较了target和shred的相等的情况是一个优化,其实在深搜的过程中还是搜索了这种情况时间也没有节省,更郁闷的是自己的优化还出现了一个很要命的bug,最后还是只好把那个自以为得意的部分给扔了…………

 

源代码:

 

//target:
//1.是否相等;
//2.比目标数小或等的最大数sum;
//////出现相同返回reject;
//////没有出现返回error;
//////出现返回 sum;

#include <iostream>
char shred[9]={0};
int target;
int CuttedNumber[9]={0};
int n;
int pro[7]={0};
int protemp[7]={0};
int sum;
int reject=-1;
using namespace std;
void CutNumber()
{
 n=strlen(shred);
 for(int i=0;i<n;i++)
  CuttedNumber[i]=(int)shred[i]-48;
 return ;
}
void changepro()
{
 for(int i=0;i<n;i++)
 {
  pro[i]=protemp[i];
 }
 return ;
}
int yforyy(int y,int yy)
{
 int temp=0;
 int ten_m=1;
 for(int i=yy;i>=y;i--)
 {
  protemp[i]=y;
  temp+=CuttedNumber[i]*ten_m;
  ten_m*=10;
 }
 return temp;
}
void search(int y,int yy, int sumtemp)
{
   sumtemp+=yforyy(y,yy);
   if(yy+1==n)
   {
    if(sum==sumtemp)
    {
     reject=sumtemp;
    }
    else if(sum<sumtemp&&sumtemp<=target)
    {
     sum=sumtemp;
     changepro();
    }
   }
   else
   {
    if(sumtemp<=target)
    {
     for(int i=0;yy+1+i<n;i++)
             search(yy+1,yy+1+i,sumtemp);
    }
    else
     return ;
   }

}
main()
{
 
 while(cin>>target>>shred&&(target!=0||shred[0]!='0'))
 {
  sum=-2;
 CutNumber();
   for(int i=0;i<n;i++)
   search(0,i,0);
   if(reject==sum)
    cout<<"rejected"<<endl;
   else if(sum==-2)
    cout<<"error"<<endl;
   else
   {
    cout<<sum<<" ";
    for(int i=0;i<n;i++)
    {
     cout<<shred[i];
     if(pro[i]!=pro[i+1]&&i+1<n)
      cout<<" ";
    }
    cout<<'\n';
   }
  reject=-1;
  memset(shred,0,sizeof(shred));
  memset(pro,0,sizeof(pro));
  memset(protemp,0,sizeof(protemp));
  memset(CuttedNumber,0,sizeof(CuttedNumber));
 }
 return 0;
}

acm | 阅读 3100 次
文章评论,共0条
游客请输入验证码
浏览255959次