Shredding Company poj 1416

Shredding Company

原文地址

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

代码：

#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;
}