[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] 1902. 「殿仁.王,不認識,誰啊?」,然後他就死了……

[NPSC] 2009初賽 E. 檸檬汽水傳說

[AtCoder] [經典競程 90 題] 024 - Select +/- One(★2)