BZOJ1026 [SCOI2009] windy 수(디지털 dp)

Ac "GT 시험"이후 이 문제는 여전히 기초적인 것 같다
[문제풀이]
먼저 수조 dp, f:dp[i][j]를 미리 처리하면 다음과 같다. i위에서 j를 채우는 windy수는 몇 개(개수는 1위, 10위는 2위...)
상태 이동: 맨 왼쪽에 한 개씩 입력:
dp[i][j]=sigma(dp[i-1][k]), 0<=k<=9 및 abs(j-k)>=2
경계: dp[1][j]=1
A에서 B까지 계수할 때 A와 B의 위치가 같지 않으면 가장 높은 위치는 0이 될 수 있다. f[i]로 i위를 가장 높은 위치로 기록하고 가장 높은 위치는 0의 windy 수를 기록한다.
그럼, f[i]=f[i-1]+sigma(dp[i-1][j]), 1<=j<=9
개수:
1. 다음에도 상계가 있고 귀찮아서 접두사와 사상을 활용할 수 있다
2. 높은 위치에서 낮은 위치까지 0~x에서 windy의 개수를 통계한다. x의 i위 수를 num[i]로 설정하고 윗자리에서num[i+1]를 채울 때(최고위 특수처리):
우선, 이 분은 0~num[i]-1, 뒤에 마음대로 채울 수 있습니다. ans+=sigma(dp[i-1][j]), i가 가장 높은 자리가 아니라면 윗사람과의 차이에 주의해야 합니다>=2
그리고 이분은num[i],ans가 다음 분과 관련되어 다음 분을 처리할 수 있습니다.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef long long LL;
LL dp[20][20]={0},f[20]={0};
void init()
{
	int i,j,k;
	f[1]=1;
	for(i=0;i<=9;i++)
		dp[1][i]=1;
	for(i=2;i<=10;i++)
	{
		for(j=0;j<=9;j++)
			for(k=0;k<=9;k++)
				if(abs(j-k)>=2) dp[i][j]+=dp[i-1][k];
		f[i]=f[i-1];
		for(j=1;j<=9;j++)
			f[i]+=dp[i-1][j];
	}
}
LL solve(int x)//  0~x-1 windy     
{
	int num[20]={0};
	LL ans=0;
	int p=0,i,j;
	while(x!=0)
	{
		num[++p]=x%10;
		x/=10;
	}
	ans=f[p];//    0
	for(i=1;i<num[p];i++)//    1~num[p]-1
		ans+=dp[p][i];
	for(i=p-1;i>=1;i--)//    num[p]，     
	{
		for(j=0;j<num[i];j++)
			if(abs(num[i+1]-j)>=2) ans+=dp[i][j];
		if(abs(num[i+1]-num[i])<2) break;
	}
	return ans;
}
int main()
{
	int A,B;
	scanf("%d%d",&A,&B);
	init();
	printf("%lld",solve(B+1)-solve(A));//  
	return 0;
}