Programing/Algorithm

poj 3176 Cow Bowling

sosal 2014. 5. 6. 08:03
반응형

/*

 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;

}

}

'Programing > Algorithm' 카테고리의 다른 글

poj 2136 Vertical Histogram  (0) 2014.05.07
poj 1218 THE DRUNK JAILER  (0) 2014.05.07
poj 2140 Herd Sums  (0) 2014.05.06
algospot - HAMMINGCODE  (0) 2014.05.06
algospot - Divisibility  (0) 2014.05.06