首页 > 代码库 > POJ 1163 The Triangle
POJ 1163 The Triangle
来源:http://poj.org/problem?id=1163
The Triangle
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 37660 | Accepted: 22611 |
Description
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (Figure 1)
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Sample Output
30
Source
IOI 1994
题意: 找一条从顶节点到底部的路径,使该路径上点之和最大,求最大值。
题解: 动态规划解决之
AC代码:
#include<cstdio> #include<cstring> const int Max=105; int max[Max][Max],sum[Max][Max],n; int DP(int i,int j){ if(~sum[i][j]) return sum[i][j]; if(i==n-1) sum[i][j]=max[i][j]; else sum[i][j]=max[i][j]+(DP(i+1,j)>DP(i+1,j+1) ? DP(i+1,j):DP(i+1,j+1)); return sum[i][j]; } int main() { memset(sum,-1,sizeof(sum)); scanf("%d",&n); for(int i=0;i<n;i++) for(int j=0;j<=i;j++) scanf("%d",&max[i][j]); printf("%d\n",DP(0,0)); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。