poj 3176 Cow Bowling

/*

 * http://sosal.tistory.com/
 * made by so_Sal
 */

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

매우 유명한 삼각형 - 역 triangle problem 입니다.

위에서부터 숫자를 더해나가면 경우의수가 매우 많아집니다.

N이 최대 350까지 주어지기 때문에, 위에서부터 더하는 경우에는 time over가 나게 됩니다.

트라이앵글을 아래에서부터 큰수먼저 더해가면서 height를 낮춰가는 방향으로

알고리즘을 구현하시면 됩니다.

입력

          7

        3   8

      8   1   0

    2   7   4   4

  4   5   2   6   5

height =0부분을 height=1부분과 합치기

          7

        3   8

      8   1   0

    5  12  10  10

height =0부분을 height=1부분과 합치기 (반복)

          7

        3   8

     20  13  10

height =0부분을 height=1부분과 합치기 (반복)

          7

       23  21

height =0부분을 height=1부분과 합치기 (반복)

         30

이 방법만 안다면 어렵지 않게 푸실 수 있는 문제입니다.

구현은 다음과 같습니다.

#include<iostream>

#include<string>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

int main(){

int N;

vector<int> v[400];

int tmp;

cin>>N;

if(N == 0){

cout<<0<<endl;

}

else if(N==1){

cin>>tmp;

cout<<tmp;

}

else{

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

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

cin>>tmp;

v[i].push_back(tmp);

}

}

for(int i=N-2;i>0;i--){

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

v[i][j] += v[i+1][j]>v[i+1][j+1]?v[i+1][j]:v[i+1][j+1];

}

}

int max = (v[1][0]+v[0][0])>(v[1][1]+v[0][0]) ? v[1][0]+v[0][0]:v[1][1]+v[0][0];

cout<<max<<endl;

}

}