首页 > 代码库 > uva10564 - Paths through the Hourglass(递推)
uva10564 - Paths through the Hourglass(递推)
题目:uva10564 - Paths through the Hourglass(递推)
题目大意:给出这样的两个数塔,然后给出一个值,问你能否从这个数塔中找到路径,路径上的值之和等于这个数,输出这样的路径的总数,如果多条打印路径先挑开始的位置(0..n - 1)最小的,如果这样还是有多条,在比较后面的向左向右字典序最小的。
解题思路:一开始两个数塔一个正着推,一个倒着推,结果数目是出来了,但是路径就难办了,最后把这两个数塔都正着推,只是状态转移方程不一样。这样路径输出就比较好处理。
代码:
#include <cstdio> #include <cstring> const int N = 50; const int maxn = 520; typedef long long ll; int n1[N][N]; int n2[N][N]; ll dp[maxn][N][N]; int n, s; void printf_ans (int num, int x, int y) { if (x == 2 * n - 2) return; if (x == 0) { printf ("%d ", y); } if (x < n - 1) {//注意 if (y && dp[num - n1[x][y]][x + 1][y - 1]) { printf ("L"); printf_ans (num - n1[x][y], x + 1, y - 1); } else if (dp[num - n1[x][y]][x + 1][y]) { printf ("R"); printf_ans (num - n1[x][y], x + 1, y); } } else { if (dp[num - n2[x - n + 1][y]][x + 1][y]) { printf ("L"); printf_ans (num - n2[x - n + 1][y], x + 1, y); } else if (dp[num - n2[x - n + 1][y]][x + 1][y + 1]) { printf ("R"); printf_ans (num - n2[x - n + 1][y], x + 1, y + 1); } } } int main () { while (scanf ("%d%d", &n, &s), n||s) { for (int i = 0; i < n; i++) for (int j = 0; j < n - i; j++) scanf ("%d", &n1[i][j]); for (int i = 1; i < n; i++) for (int j = 0; j <= i; j++) scanf ("%d", &n2[i][j]); n2[0][0] = n1[n-1][0]; memset (dp, 0, sizeof (dp)); //init for (int i = 0; i < n; i++) dp[n2[n - 1][i]][2 * n - 2][i] = 1; //递推 :从下往上推 for (int i = n - 2; i >= 0; i--) for (int j = 0; j <= i; j++) for (int m = n2[i][j]; m <= s; m++) { dp[m][i + n - 1][j] = dp[m - n2[i][j]][i + n][j] + dp[m - n2[i][j]][i + n][j + 1]; } for (int i = n - 2; i >= 0; i--) for (int j = 0; j < n - i; j++) for (int m = n1[i][j]; m <= s; m++) { dp[m][i][j] = dp[m - n1[i][j]][i + 1][j]; if (j) dp[m][i][j] += dp[m - n1[i][j]][i + 1][j - 1]; } //总路径数目 ll ans = 0; for (int i = 0; i < n; i++) { if (dp[s][0][i]) ans += dp[s][0][i]; //printf ("%lld\n", dp[s][0][i]); } if (!ans) printf ("%lld\n\n", ans); else { printf ("%lld\n", ans); for (int i = 0; i < n; i++) if (dp[s][0][i]) {//起始位置最小的 printf_ans(s, 0, i); break; } printf ("\n"); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。