「オイラープロジェクト61~70」の編集履歴(バックアップ)一覧に戻る

オイラープロジェクト61~70 - (2012/08/26 (日) 16:23:01) の編集履歴(バックアップ)


問い67

http://projecteuler.net/problem=67
三角形に並んだ数字を上から下へ向かいながら途中の経路の計が最高になるルートの合計値を見つけよという問題。
問い18のコードのサイズを少し変更するだけで作成可能。




#include<stdio.h>
#include<algorithm>
#include<string.h>
int main(){
int memo[2][101],a,now,next;
sizeof(memo,0,sizeof(memo));
scanf("%d",&memo[0][0]);
for(int i=1;i<100;i++){
	now =(i+1)%2;
	next=i%2;
	for(int j=0;j<=i;j++){
		scanf("%d",&a);
		if(j==i){
			memo[next][j]=memo[now][j-1]+a;
		}else if(j>0&&j<i){
			memo[next][j]=std::max(memo[now][j-1],memo[now][j])+a;
		}else{
			memo[next][j]=memo[now][j]+a;
		}
	}
}
int ans=0;
for(int i=0;i<100;i++)ans=std::max(ans,memo[next][i]);
printf("%d\n",ans);
}