Shredding Company poj 1416

Shredding Company

原文地址

解题思路 ： 暴搜 dfs
用两个字符串存储目标和剪切串
利用stl的string的substr截取k到l 然后转换成数字填入一个vector数组中，枚举出来的每一种方案都存到map<int,vector< int> > 中 顺便纪录一下ans 和ansf ansf代表着重复次数

代码：

#include<iostream>
#include<map>
#include<vector>
#define int long long
using namespace std;
string a,b;
int ai,bi;
int ans,ansf;
map<int,vector<int> > mp;
vector<int> d;
inline int toint(string s){
    int tt(0);for(int i=0;i<s.size();i++) tt=tt*10+s[i]-'0';return tt;
}
void dfs(int k,int v){
    if(v>ai) return;if(k==b.size()){
    if(ans<v){
    ans = v,ansf = 0;for(int i=0;i<d.size();i++)mp[ans].push_back(d[i]);}else if(ans==v){
    ansf++;}return;}int i(1);while(k+i<=b.size()){
    int t = toint(b.substr(k,i));if(t+v>ai) break;d.push_back(t);dfs(k+i,t+v);d.pop_back();i++;}
}
signed main(){
    while(cin>>a>>b&&a!="0"&&b!="0"){
    ai = toint(a);bi = toint(b);if(ai==bi) {
    cout<<a<<" "<<b<<endl;
// }else if(ai>bi){
    
// cout<<"error"<<endl;}else{
    d.clear(); mp.clear();ans = 0;ansf = 0;dfs(0,0);if(ansf){
    cout<<"rejected"<<endl;}else if(ans!=0){
    cout<<ans;for(int i=0;i<mp[ans].size();i++){
    cout<<" "<<mp[ans][i];} cout<<endl;}else{
    cout<<"error"<<endl;}}}return 0;
}