首页 > 代码库 > poj1416
poj1416
看这个解感觉有好多地方写的很妙
膜啊,大神,学习了
哦,我做错了,方法还繁
使用矩阵表示所有可能值
假设要剪碎的是 12346
矩阵num为:
1 12 123 1234 12346
2 23 234 2346 0
3 34 346 0 0
4 46 0 0 0
6 0 0 0 0
原博客:http://blog.csdn.net/non_cease/article/details/7326850
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; #define M 6 int d[M], tar, val, len, num[M][M]; bool flag; struct PathCell { int l, r; } pre[M][M], ans; //记录路径 void convert(char tmp[]) { int i; for (i = 0; tmp[i] != ‘\0‘; i++) d[i] = tmp[i] - ‘0‘; len = i; } void preprocess()//预处理,求出剪断后的所有可能整数 { int i, j, k; for (i = 0; i < len; i++) { for (j = i; j < len; j++) { k = i; while (k <= j) { num[i][j] = num[i][j] * 10 + d[k]; k++; } } } } bool dfs(int id, int now, int last) { if (id >= len) { if (now > val && now <= tar) { val = now; ans.l = last; ans.r = id - 1; //当获得最优值时,ans记录最后的情况,用于输出路径,flag更新为false,表明目前只有一种方式取得最优值 flag = false; return true; //返回true,表明找到最优值 } else if (now == val) flag = true;//flag为true表示当前最优值可通过多种方式获得 return false; } bool mark = false; for (int i = 1; i <= len - id; i++) { int cur = id+i-1; if (dfs (id + i, now + num[id][cur], id)) {//返回值为true时(即找到当前最优指时)记录路径 pre[id][cur].l = last; pre[id][cur].r = id - 1; mark = true; } } return mark; } void output(int l, int r) //递归输出路径 { if (l < 0 && r < 0) return; output(pre[l][r].l, pre[l][r].r); printf ("%d ", num[l][r]); } int main() { char tmp[10]; while (scanf ("%d %s", &tar, tmp)) { if (!tar && tmp[0] == ‘0‘) break; memset(num, 0, sizeof (num)); convert(tmp); preprocess(); flag = false; val = -1; dfs(0, 0, -1); if (flag) { printf ("rejected\n"); continue; } if (val == -1) printf ("error\n"); else { printf ("%d ", val); output (ans.l, ans.r); printf ("\n"); } } return 0; }
poj1416
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。