首页 > 代码库 > [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)