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

題目連結:http://tioj.infor.org/problems/1288http://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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology