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

オイラープロジェクト61~70 - (2012/08/26 (日) 16:23:01) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

+*問い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);
+ }