HDU 1539 Shredding Company(数位 DFS)

    技术2025-12-28  5

     

     题意:给出数字 n 和一个字符串,要求切割字符串,然后把他们的和加起来,找到一个比目标值小 但 尽可能接近目标值的和。

    如果有多于一个这样组合的和就输出rejected,如果无法组成比它小的数则输出error,否则输出那个值 并 输出解决方案

    const int N=20+5; int n,m,t; int i,j,k; char s[N]; int a[N]; //记录可能的答案 int ans[N],ans_num; //记录最后的答案 int flag,len,num,maxx; void DFS(int sum,const int pos) //sum 代表当前的和,pos 代表已经切割到的位置 { if(sum>k) return ; if(pos==len){ if(maxx<=sum && sum<=k){ if(sum==maxx) flag=2; else{ maxx=sum; flag=1; //debug(num); ans_num=num; for(int i=0;i<num;i++) ans[i]=a[i]; } } return ; } int tmp=0; for(int i=pos;i<len;i++){ tmp=tmp*10+s[i]-'0'; a[num++]=tmp; DFS(tmp+sum,i+1); num--; } return ; } int main() { //IOS; while(~sd(k)){ ss(s); if(k==0 && s[0]=='0') break; len=strlen(s); maxx=0,flag=0,num=0; DFS(0,0); if(flag==0) puts("error"); else if(flag==2) puts("rejected"); else{ printf("%d",maxx); for(int i=0;i<ans_num;i++){ printf(" %d",ans[i]); } puts(""); } } //PAUSE; return 0; }

     

    Processed: 0.008, SQL: 10