これも定番問題かな。
http://community.topcoder.com/stat?c=problem_statement&pm=11626
問題
ある整数の幸せ度は、桁中の4の登場回数と7の登場回数の差分の絶対値である。
2つの整数A、Bが与えられたとき、整数A~Bの幸せ度の総和を求めよ。
解法
0~x-1までの幸せ度の総和をf(x)とすると、f(B+1)-f(A)が解答。
ではf(x)をどう求めるか。
まず、leading zeroも含め、i桁の数において4と7の登場回数の差がdとなるような数をDPで求める。
これは桁を増やすたびに4,7,それ以外を追加していけば簡単に求まる。
数xの最大桁の値がyとすると、最大桁を0~(y-1)にしたときの幸せ度の和は、前期DPの結果を用いて、それ以下の桁の幸せ度の総和を求めることができる。
また、最大桁yの時の幸せ度は、xの最大桁からyを引く、すなわち最大桁を除いた残りの数における幸せ度を再帰的に求めていけばよい。
ただ、y=4,7の時は以下の桁の幸せ度の和を求めるとき、4,7の数が増減することに注意する。
class SumOfLuckiness { public: ll dp[11][22]; ll sum(ll S, int keta, int dif) { int i,j; ll t=1,ret=0; if(keta<0) return 0; FOR(i,keta) t*=10; FOR(i,10) { if(S<(i+1)*t) return ret + sum(S-(i*t),keta-1,dif+(i==4)-(i==7)); FOR(j,22) ret += abs((j-10)+dif+(i==4)-(i==7))*dp[keta][j]; } return ret; } long long theSum(int A, int B) { int i,j; ZERO(dp); dp[0][10]=1; FOR(i,10) for(j=1;j<=19;j++) { dp[i+1][j+1]+=dp[i][j]; dp[i+1][j-1]+=dp[i][j]; dp[i+1][j] +=8*dp[i][j]; } return sum(B+1,9,0)-sum(A,9,0); } };