Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
参考了其他人的答案,写出的!附代码#include <iostream> using namespace std; const int Maxsize = 1000000; int path; // 最优划分的划分方式 int p; // 某种划分方式 int target; // 目标值 int visit[Maxsize]; // 记录每个sum出现的次数,数组尽量开大一点 int sum; // 某种划分方式的和 int result; // 最优划分方式的和 double pow(int i, int j) //计算幂函数 { double ret = 1; while(j--) { ret *= i; } return ret; } int getlen(int n) // 得到n的位数 { if(n < 10) return 1; else if(n < 100) return 2; else if(n < 1000) return 3; else if(n < 10000) return 4; else if(n < 100000) return 5; else return 6; } int getvalue(char* s, int i) // 得到数字字符串s前i位字符的数值 { int k = i; int sum = 0; while(k) { k--; sum += (s[k] - '0')*(int)pow(10, (i-k-1)); } return sum; } int gethead(int n, int i) // 得到由n的前i位数字构成的int { int len = getlen(n); if(len < i) return n; return n/(int)pow(10, (len - i)); } int gettail(int n, int i) // 得到由n的后i位数字构成的int { return n % (int)pow(10,i); } void dfs(char* s, int len) { if(len == 0) { visit[sum]++; // 标记 if(sum > result && sum <= target) { result = sum; path = p; } return; } for(int i = 1; i <= len; i++) { int a = getvalue(s, i); // n的前i位字符转变为数字留下 sum += a; // 部分和 if(sum > target) // 剪枝,部分和已经大于target,无需向下搜索 { sum -= a; continue; } p = p * 10 + i; // 记录划分方式 char b[7]; // 构造n的后i位字符序列,继续递归 int j = 0; for(int k = i; k < len; k++) { b[j++] = s[k]; } b[j] = '\0'; dfs(b, len - i); sum -= a; 回溯 p /= 10; } return; } int main() { char s[7]; while(cin >> target >> s) { int len = strlen(s); int n = getvalue(s, len); if(!target && !n) // 边界条件 break; if(target == n) // 目标值与打印纸上的数字一致 { cout << target << " " << n << endl; continue; } int num = n; // 定义临时变量 int k = 0; // n的各位数字之和 while(num) { k += num % 10; // 逐位划分是和的最小划分方式 num /= 10; } if(k > target) // { cout << "error" << endl; continue; } // Initial result = -1; sum = 0; path = 0; p = 0; memset(visit, 0, sizeof(visit)); // DFS dfs(s, len); // output if(visit[result] > 1) cout << "rejected" << endl; else if(visit[result] == 1) { cout << result << " "; int l = getlen(path); for(int i = 1; i <= l; i++) { int k = gethead(path, 1); cout << gethead(n, k) << " "; n = gettail(n, len -= k); path = gettail(path, l - i); } cout << endl; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator