Cow Bowling(动态规划)
发布日期:2021-10-16 05:05:09 浏览次数:8 分类:技术文章

本文共 1647 字,大约阅读时间需要 5 分钟。

Cow Bowling
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 19855   Accepted: 13164

Description

The cows don't use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this:
7        3   8      8   1   0    2   7   4   4  4   5   2   6   5
Then the other cows traverse the triangle starting from its tip and moving "down" to one of the two diagonally adjacent cows until the "bottom" row is reached. The cow's score is the sum of the numbers of the cows visited along the way. The cow with the highest score wins that frame.
Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable.

Input

Line 1: A single integer, N
Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle.

Output

Line 1: The largest sum achievable using the traversal rules

Sample Input

573 88 1 02 7 4 44 5 2 6 5

Sample Output

30

Hint

Explanation of the sample:
7         *        3   8       *      8   1   0       *    2   7   4   4       *  4   5   2   6   5
The highest score is achievable by traversing the cows as shown above.

Source

题意:

求一条路径,使从头到尾和最大。

思路:

简单动态规划。

代码:

#include 
#include
#include
using namespace std;int num[550][550],f[550][550];int sum;int main(){ int i,j; int n; cin>>n; for(i=1;i<=n;i++) { for(j=1;j<=i;j++) cin>>num[i][j]; } for(j=1;j<=n;j++)f[n][j]=num[n][j]; for(i=n-1;i>=1;i--) { for(j=1;j<=i;j++) f[i][j]=num[i][j]+max(f[i+1][j],f[i+1][j+1]); } cout<
<

转载地址:https://blog.csdn.net/sinat_37668729/article/details/77070883 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Satellite Photographs(dfs)
下一篇:Bovine Birthday(思维题)

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月26日 18时25分07秒