POJ 3176 Cow Bowling 题解 《挑战程序设计竞赛(第2版)》 � 码农场

http://poj.org/problem?id=3176

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

http://www.hankcs.com/program/cpp/poj-3176-cow-bowling.html

2.3 记录结果再利用的"动态规划" 基础的动态规划算法

POJ 3176 Cow Bowling

奶牛保龄球：金字塔形的保龄球中从顶往下撞击，每次只能撞击左下或右下两个，求所有撞到得分的最高值。

最基础的dp吧，用dp[i][j]表示第i行第j个点处能得到的最高分，由顶往下推导更新此dp即可：

#define MAX_CASES 350

int score[MAX_CASES][MAX_CASES];

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int N;

    cin >> N;

    for (int i = 0; i < N; ++i)

    {

        for (int j = 0; j <= i; ++j)

        {

            cin >> score[i][j];

        }

    }

    dp[0][0] = score[0][0];

    for (int i = 0; i < N - 1; ++i)

    {

        for (int j = 0; j <= i; ++j)

        {

            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + score[i + 1][j + 1]);

            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + score[i + 1][j]);

        }

    }

    cout << *max_element(dp[N -1], dp[N -1] + N) << endl;

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

Read full article from POJ 3176 Cow Bowling 题解 《挑战程序设计竞赛(第2版)》 � 码农场