プロジェクトオイラー問150 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20150
三角形に並んだ数表を生成して、三角形で範囲を区切った時その中の数字の和が最小になる三角形を見つけその和をこたえる問題。
単なるメモ化計算と動的計画法の組み合わせで数秒の計算で答えが出ます。

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<iostream>
const int LIMIT=1000;
__int64 dp1[LIMIT+1][LIMIT+1],dp3[LIMIT+1][LIMIT+1];
int MOD=pow(2,20);
int D=pow(2,19);

int main(){
	memset(dp1,0,sizeof(dp1));
	__int64 ans=273519;//s1を仮の答えとする
	__int64 t=0;
	for(int i=1;i<=LIMIT;i++){
		__int64 sum=0;
		__int64 dp2[LIMIT+1];
		dp2[0]=0;
		for(int j=1;j<=i;j++){
			t=(615949*t+797807)%MOD;
			sum+=(t-D);
			dp2[j]=sum;
		}
		
		memset(dp3,0,sizeof(dp3));
		for(int j=1;j<=i;j++){
			for(int k=0;k<j;k++){
				__int64 t=dp1[j-1][k]+dp2[j]-dp2[k];
				ans=std::min(t,ans);
				dp3[j][k]=t;
			}
		}
		memcpy(dp1,dp3,sizeof(dp3));
	}
	std::cout<<ans;
}