专栏首页饶文津的专栏【POJ 3176】Cow Bowling(DP)

【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]表示第i行第j列的最大值

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;
}

逆向:逆着从n-1行到第1行,每次比较下方和右下方的大小,大的加上去,最后输出a[1][1]即可。

#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...

    风骨散人Chiam
  • 背包九讲之分组背包-HDU1712题解

    以杭电1712为例子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...

    ShenduCC
  • 【PAT甲级】Friend Numbers

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

    喜欢ctrl的cxk
  • 洛谷P2870 [USACO07DEC]最佳牛线,黄金Best Cow Line, Gold

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

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

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

    风骨散人Chiam
  • pta 习题集 5-5 最长连续递增子序列 (dp)

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

    ShenduCC

扫码关注云+社区

领取腾讯云代金券