首页 > 代码库 > 【bzoj1026】 SCOI2009—windy数

【bzoj1026】 SCOI2009—windy数

http://www.lydsy.com/JudgeOnline/problem.php?id=1026 (题目链接)

题意

  在区间${[A,B]}$有多少个数相邻两个数位上的数之差至少为2。

Solution

  数位dp,右转题解:LCF

  其中${f[i][0]}$,表示的是第${i}$位为${0}$的方案数,并不是不取${i}$位。

细节

  LL

代码

// bzoj1026#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<ctime>#define LL long long#define inf (1ll<<30)#define MOD 1000000007#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;LL f[20][10],g[20],ans;int n,a[2],t[20];LL solve(int p) {	memset(f,0,sizeof(f));	memset(g,0,sizeof(g));	for (n=0;a[p];a[p]/=10) t[++n]=a[p]%10;	for (int i=0;i<10;i++) f[1][i]=1;	for (int i=2;i<=n;i++)		for (int j=0;j<10;j++)			for (int k=0;k<10;k++) if (abs(j-k)>1) f[i][j]+=f[i-1][k];	g[1]=1;	for (int i=2;i<=n;i++) {		for (int j=0;j<t[i-1];j++)			if (abs(t[i]-j)>=2) g[i]+=f[i-1][j];		if (abs(t[i]-t[i-1])>1) g[i]+=g[i-1];	}	LL res=0;	for (int i=1;i<n;i++) 		for (int j=1;j<10;j++) res+=f[i][j];	for (int i=1;i<t[n];i++) res+=f[n][i];	return res+g[n];}int main() {	scanf("%d%d",&a[0],&a[1]);a[0]--;	ans-=solve(0);	ans+=solve(1);	printf("%lld",ans);	return 0;}

 

【bzoj1026】 SCOI2009—windy数