「オイラープロジェクト141～150」の編集履歴（バックアップ）一覧に戻る

---

「オイラープロジェクト141～150」を以下のとおり復元します。

---

*問い150
http://projecteuler.net/problem=150


理論値　計算量O(100万＾３)、メモリは__int64で100万個と少しばかりの配列を消費で解法。
少しばかりめんどくさかったがまあ動的計画法としては単純。


 #include<stdio.h>
 #include<iostream>
 #include<string.h>
 __int64 memo[1002][1002],sum[1001]={0};
 int main(){
 	__int64 ans=273519,s,t=0,m20=(1<<20),m19=(1<<19),d;
	memset(memo,0,sizeof(memo));
 	for(int r=1;r<=1000;r++){
 		memset(sum,0,sizeof(sum));
 		for(int c=1;c<=r;c++){
			t=(615949*t+797807)%m20;
 			sum[c]=sum[c-1]+t-m19;
 		}
 		for(int c=r;c>0;c--){
 			for(int c2=0;c2<c;c2++){
 				d=sum[c]-sum[c2];
 				memo[c][c-c2]=d+memo[c-1][c-c2-1];
 				if(ans>memo[c][c-c2])ans=memo[c][c-c2];
 			}
 		}
 	}
 	std::cout<<ans<<"\n";
 }

---

復元してよろしいですか？