USACO training course Number Triangles 数塔DP oj10122

题目大意：

...就是数塔

　　      7     　　   3   8    　　 8   1   0  　  2   7   4   4　4   5   2   6   5

7+3+8+7+5=30

Sample Input

573 88 1 02 7 4 44 5 2 6 5212 3

Sample Output

304

DP水题 记录一下

自下往上走 左右始终选择较大的与之上的相加

#include<iostream> #include<algorithm> #include<stdio.h> #include<cstring> using namespace std; int dp[1005][1005]; int main() { int t; while(~scanf("%d",&t)) { memset(dp,0,sizeof(dp)); for(int i=1;i<=t;i++) for(int j=1;j<=i;j++) scanf("%d",&dp[i][j]); for(int i=t-1;i>=1;i--) for(int j=1;j<=i;j++) dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]); printf("%d\n",dp[1][1]); } return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/8893773.html