ACM学習-POJ-1163-The Triangle

菜鳥はACMを学び、自分の成長過程の点滴を記録する.
勉強の道中、君と一緒に勉強する.
ACM学習-POJ-1163-The Triangle
The Triangle
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 34125
 
Accepted: 20303
Description

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

(Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right. 
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input

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

Sample Output

30

Source
IOI 1994
タイトルの要件:
n層の三角形を入力し、i層目にi個の数があり、1層目からn層目までのすべてのルートのうち、重み値の和が最大のルートを求める.規定:第i層のある数は、第i+1層の中でその位置に隣接する2つの数のうちの1つにしか接続できない.テーマ分析:
典型的な動的計画.
したがって,下から上へ押すことができ,隣接する2つの数のうちより大きなものを上位に加算し,結果として隣接する2つの数のうちより大きなものを上位に加算し,このように推定することができる.2 D配列arr_を使用[][]下からその点までの最大値を記録します.
コアコード
arr_[i][j] += arr_[i+1][j] > arr_[i+1][j+1] ? arr_[i+1][j] : arr_[i+1][j+1];
最後の結果はarr_[0][0].
以下、ACコードを示す.

#include 
#define MAXSIZE 105
int main()
{
    int n;
    int i, j;
    int arr_[MAXSIZE][MAXSIZE];
    while (~scanf("%d", &n))
    {
        for (i=0; i=0; i--)
        {
            for (j=0; j<=i; j++)
            {
                arr_[i][j] += arr_[i+1][j] > arr_[i+1][j+1] ? arr_[i+1][j] : arr_[i+1][j+1];
            }
        }
        
        printf("%d", arr_[0][0]);
    }
    return 0;
}