TopCoder SRM 300 Div1 Medium JumpyNum

問題

jumpy numberとは、隣り合う桁の数字の差の絶対値が全て2以上であるような数を言う。
low以上high以下のjumpy numberの数を求めよ。

制約条件

low,high≦2*10^9

方針

n以下のjumpy numberの数が求まればよい。
上の桁から一桁ずつ見ていく典型的なDPをする。

dp[i][j][smaller][nonzero]を、
i桁目まで見て、最後の数字がjで、
smaller=1なら今までにnの数字よりも小さい数字が出て、
nonzero=1なら今までに0でない数字が出たような状態の場合の数とする。

これに次の桁の数を0〜9まで考えてテーブルを更新していけばいい。

ソースコード

int d[20],n;
int dp[20][10][2][2];

int calc(int m){
	for(n=0;m;m/=10)d[n++]=m%10;
	reverse(d,d+n);
	memset(dp,0,sizeof(dp));
	dp[0][0][0][0]=1;
	rep(i,n)rep(j,10)rep(k,2)rep(l,2){
		rep(nj,10)if(k||nj<=d[i])if(abs(nj-j)>1||l==0){
			int nk=k||nj<d[i], nl=l||nj;
			dp[i+1][nj][nk][nl]+=dp[i][j][k][l];
		}
	}
	int res=0;
	rep(i,10)rep(j,2)res+=dp[n][i][j][1];
	return res;
}

class JumpyNum {
	public:
	int howMany(int low, int high) 
	{
		return calc(high)-calc(low-1);
	}
};