首页 > 代码库 > [POJ1416]Shredding Company(dfs)
[POJ1416]Shredding Company(dfs)
题目链接:http://poj.org/problem?id=1416
题意:一段数分成好几段相加,求最大的且不大于目标值的组合。
DFS,用vector<int>tmp来记录中间结果,回溯的时候pop掉。判重用了个map,其实用一个flag打标记也可。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <cassert> 8 #include <cstdio> 9 #include <bitset>10 #include <vector>11 #include <deque>12 #include <queue>13 #include <stack>14 #include <ctime>15 #include <set>16 #include <map>17 #include <cmath>18 19 using namespace std;20 21 const int maxn = 32;22 int digit[maxn];23 map<int,int> vis;24 int n, aim;25 int len, ret;26 vector<int> ans, tmp;27 28 int sum(int x, int y) {29 int ret = 0;30 while(x <= y) {31 ret *= 10;32 ret += digit[x++];33 }34 return ret;35 }36 37 void dfs(int cur, int pos) {38 if(cur > aim) return;39 if(pos > len) {40 if(cur <= aim) {41 if(ret <= cur) {42 ret = cur; vis[ret]++;43 ans.clear();44 for(int i = 0; i < tmp.size(); i++) {45 ans.push_back(tmp[i]);46 }47 }48 }49 return;50 }51 for(int i = pos; i <= len; i++) {52 int x = sum(pos, i);53 tmp.push_back(x);54 dfs(cur+x, i+1);55 tmp.pop_back();56 }57 }58 59 void f(int x) {60 len = 0;61 vector<int> s;62 while(x) {63 s.push_back(x%10);64 x /= 10;65 }66 for(int i = s.size() - 1; i >= 0; i--) {67 digit[++len] = s[i];68 }69 tmp.clear();70 dfs(0, 1);71 }72 73 int main() {74 // freopen("in", "r", stdin);75 while(~scanf("%d%d",&aim,&n)&&aim+n) {76 if(aim >= n) {77 printf("%d %d\n",n, n);78 continue;79 }80 ret = -1; vis.clear();81 f(n);82 if(ret == -1) puts("error");83 else if(vis[ret] >= 2) puts("rejected");84 else {85 printf("%d ", ret);86 for(int i = 0; i < ans.size(); i++) {87 if(i) printf(" ");88 printf("%d", ans[i]);89 }90 printf("\n");91 }92 }93 return 0;94 }
[POJ1416]Shredding Company(dfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。