巢穴

about:blank

P1416

从大到小枚举能组成的值.dfs.水题

#include <iostream>
#include <string>
using namespace std;

int x;
string y;
int count_;
int rs,sr;
int stop,v;
int value[100],result[100];
void dfs(int p,int sum,int v_)
{
 if (sum==stop&&p==y.length()&&v_==v)
 {
  for (int i=0;i<v_;i++)
   result[i]=value[i];
  rs=v;
  count_++;
  sr=stop;
  return;
 }
 if (sum>stop) return;
 if (v_>v) return;
 if (p>=y.length()) return;
 for (int i=p;i<y.length();i++)
 {
  //if ((i-p+1>1)&&y[i]=='0') continue;
  int s=0;
  for (int j=p;j<=i;j++)
  {
   s=s*10+y[j]-'0';
  }
  value[v_]=s;
  dfs(i+1,sum+s,v_+1);
 }
}
void solve()
{
 for (int i=x;i>=0;i--)
 {
  count_=0;
  for (int j=1;j<=y.length();j++)
  {
      stop=i;
      v=j;
      dfs(0,0,0);
      
  }
  if (count_>1)
  {
   cout<<"rejected"<<endl;break;
  }
  if (count_==1)
  {
   cout<<sr;
   for (int k=0;k<rs;k++)
   {
    cout<<" "<<result[k];
   }
   cout<<endl;
   break;
  }
}
  if (count_==0)
  {
   cout<<"error"<<endl;
  }
  
  
 
}
int main()
{
 while(true)
 {
  cin>>x>>y;
  if (0==x&&"0"==y) break;
  solve();
 }
 
// system("pause");
  return 0;
 
}

posted on 2009-11-04 12:44 Vincent 阅读(77) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理