[TIOJ] 1288. D. [IOI 1994] 三角旅行 / [IOJ] 4. 石頭

題目連結:http://tioj.infor.org/problems/1288或http://ioj.infor.org/problems/4

---

如果你用bottom-up思考方式想這題會發現這題很簡單，因為他要拿最多的石頭，所以必定是挑他下面那兩個比較大的，因此就把所有相鄰的兩個數相加後併到上面，重複做直到沒有上面為止，那那個數就是答案

#include <stdio.h>
#include <vector>

using namespace std;

vector<int> tri[110];

int main(){
	int size;
	scanf("%d",&size);
	for(int i=0;i<size;i++){
		for(int j=0;j<=i;j++){
			int temp_inp;
			scanf("%d",&temp_inp);
			tri[i].push_back(temp_inp);
		}
	}
	for(int i=size-1;i>0;i--){
		for(int j=0;j<i;j++){
			if(tri[i][j] > tri[i][j+1]){
				tri[i-1][j] += tri[i][j];
			}else{
				tri[i-1][j] += tri[i][j+1];
			}
		}
	}
	printf("%d",tri[0][0]);
	return 0;
}