首页 > 代码库 > HLG 1813 小乐乐要下山 (dp)
HLG 1813 小乐乐要下山 (dp)
链接: http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1813
Description
上学的路总是那么艰辛,在小乐乐辛苦的出了家门之后,她才想起自己的家已经搬到山上了(睡的真迷糊)。下山的路同样十分艰难,不同的地方通行的难易程度也不同。如图所示,小乐乐现在在山顶上,她面前有两条路,每条路通往一个地点,每个地点有一个值,表示这个通行的难易程度。最底层的地点就是山脚了。大家知道,小乐乐好懒好懒的,她想知道怎么下山最省力?
Input
第一行一个整数n(1<n<500)
随后n行,第i+1行有i个数字
表示山上的路况
Output
输出从山顶到山脚最省力的路。(保证答案唯一)
Sample Input
3
1
2 5
5 6 3
Sample Output
1 2 5
Hint
输入的是一个三角形,每个点能走到下面那个点和下右那个点。
代码如下:
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <set> #include <algorithm> #define MAXN 505 #define RST(N)memset(N, 0, sizeof(N)) using namespace std; int a[MAXN][MAXN], d[MAXN][MAXN], f[MAXN], n; int min(int a, int b) { return a < b ? a : b; } void Init() { for(int i=1; i<=n; i++) { for(int j=1; j<=i; j++) { scanf("%d", &a[i][j]); } } } int main() { while(~scanf("%d", &n)) { Init(); for(int i=1; i<=n; i++) d[n][i] = a[n][i]; for(int i=n-1; i>=1; i--) { for(int j=1; j<=i; j++) { d[i][j] = a[i][j] + min(d[i+1][j], d[i+1][j+1]); } } int x = 1; f[0] = a[1][1]; int i = 2, j = 1; while(i <= n) { if(d[i][j] < d[i][j+1]){ f[x++] = a[i][j]; i++; }else { f[x++] = a[i][j+1]; i++, j++; } } for(int xx=0; xx<x; xx++) { if(xx == 0) printf("%d", f[xx]); else printf(" %d", f[xx]); } puts(""); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。