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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20164

Problem 164 「どの連続した3桁の和も与えられた数を超えない数」 †
どの連続した3桁の和も9以下のような(9以下は9を含む)20桁の数(先頭の0は認めない)はいくつあるか?

何も考えない漸化式で解けます。
試行時間１分
記述時間５分
計算時間１秒

#include<stdio.h>
#include<iostream>
#include<string.h>

int main(){
	__int64 dp[10][10];
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=9;i++){
		for(int j=0;j+i<=9;j++){
			dp[i][j]++;
		}
	}
	for(int k=3;k<=20;k++){
		__int64 next[10][10]={0};
		for(int i=0;i<=9;i++){
			for(int j=0;j+i<=9;j++){
				for(int l=0;i+j+l<=9;l++){
					next[j][l]+=dp[i][j];
				}
			}
		}
		memcpy(dp,next,sizeof(next));
	}
	__int64 ans=0;
	for(int i=0;i<=9;i++){
		for(int j=0;j+i<=9;j++){
			ans+=dp[i][j];
		}
	}
	std::cout<<"ans="<<ans<<"\n";
}