# 【POJ 3176】Cow Bowling（DP）

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

```5
7
3 8
8 1 0
2 7 4 4
4 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.

dp[i][j]=max{dp[i-1][j],dp[i-1][j-1]}+a[i][j].

```#include<stdio.h>
#include<algorithm>
using namespace std;
int n,a[355][355],ans[355][355],maxans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
ans[i][j]=max(ans[i-1][j],ans[i-1][j-1])+a[i][j];
maxans=max(ans[i][j],maxans);
}
}
printf("%d",maxans);
return 0;
}```

```#include<stdio.h>
#include<algorithm>
using namespace std;
int n,i,j,a[355][355];
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
scanf("%d",&a[i][j]);
for(i=n-1;i>=1;i--)
for(j=1;j<=i;j++)
a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
printf("%d",a[1][1]);
return 0;
}```

0 条评论

• ### 【HDU 4305】Lightning（生成树计数）

There are N robots standing on the ground (Don't know why. Don't know how).

• ### 【 Gym - 101138J 】Valentina and the Gift Tree(树链剖分)

n个节点的一棵树，每个节点的权值为g，q个询问，树上的节点U-V，求U到V的路径的最大子段和。

• ### 【HDU 4408】Minimum Spanning Tree（最小生成树计数）

XXX is very interested in algorithm. After learning the Prim algorithm and Krusk...

• ### CF思维联系–CodeForces - 222 C Reducing Fractions(数学+有技巧的枚举）

ACM思维题训练集合 To confuse the opponents, the Galactic Empire represents fractions i...

• ### 背包九讲之分组背包－ＨＤＵ１７１２题解

以杭电１７１２为例子http://acm.hdu.edu.cn/showproblem.php?pid=1712

• ### HOJ 2317 Pimp My Ride(状态压缩DP)

Pimp My Ride My Tags (Edit) Source : TUD 2005 Time limit : 3 sec Me...

• ### 【PAT甲级】Friend Numbers

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 洛谷P2870 [USACO07DEC]最佳牛线，黄金Best Cow Line, Gold

题目描述 FJ is about to take his N (1 ≤ N ≤ 30,000) cows to the annual"Farmer of the...

• ### 图论--网络流--最大流--POJ 1698 Alice's Chance

Alice, a charming girl, have been dreaming of being a movie star for long. Her c...

• ### pta 习题集 5-5 最长连续递增子序列 （dp）

Count the Sheep Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/6...