首页 > 代码库 > UVA - 624CD(递推+ 路径打印)
UVA - 624CD(递推+ 路径打印)
题目: UVA - 624CD(递推+ 路径打印)
题目大意:给出一组数据,给定一个N,问这些数据能否拼凑出不大于N的最接近N的数据,可以的话输出最接近N的数据,并且打印出最长路径(要求要找输入的顺序)。
解题思路:dp【j】:代表凑出J这个数值最多需要几个数。d【j】 = Max (d【j - v【i】】 + 1。
打印路径,如果取得是最小值,那么顺着dp标记的值的减小就可以找到路径,但是取的是最大值,这样它的下一个并不能直接靠dp数组的值来判断,而是要判断到最后是否最终的值等于0。用回溯。
代码:
#include <cstdio> #include <cstring> const int N = 1000005; const int M = 25; int visit[M]; int v[N]; int dp[N]; int n, k; int Max (const int a, const int b) { return a > b? a: b; } void init () { dp[0] = 0; for (int i = 1; i <= n; i++) dp[i] = -1; } bool printf_ans (int m, int l) { if (!m) return true; for (int i = l; i < k; i++) if (m - v[i] >= 0 && dp[m - v[i]] != -1) { visit[i] = 1; if (printf_ans (m - v[i], i + 1)) return true; visit[i] = 0; } return false; } int main () { while (scanf ("%d", &n) != EOF) { scanf ("%d", &k); for (int i = 0; i < k; i++) scanf ("%d", &v[i]); init (); for (int i = 0; i < k; i++) for (int j = n; j >= v[i]; j--) { if (dp[j - v[i]] != -1) dp[j] = Max (dp[j - v[i]] + 1, dp[j]); } int i; for (i = n; i >= 0; i--) if (dp[i] != -1) break; memset (visit, 0, sizeof (visit)); printf_ans(i, 0); for (int j = 0; j < k; j++) if (visit[j]) printf ("%d ", v[j]); printf ("sum:%d\n", i); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。