数位DP和BZOJ1026题解

tonyfang posted @ 2015年8月14日 21:10 in BZOJ , 288 阅读

数位DP,一般的套路是

$f_{i,j}$表示长度为$i$,最高位为$j$的...数的个数

一般会考区间计数,这时候需要一个函数来利用$f$的值计算区间$(0,a)$或$(0,a]$的解,

然后只要调用$calc(b)-calc(a-1)$或$calc(b+1)-calc(a)$即可,其中,$calc$为上文提到的计算函数。

例题为BZOJ 1026 windy数。

本题,按照传统数位DP,设$f_{i,j}$表示长度为$i$,最高位为$j$的windy数的个数。

那么首先枚举$i$,$j$;然后枚举第$i-1$位数时的最高位$k$即可。这里预处理的DP是$O(n^3)$的。

那么后面来推$calc$函数。

先计算长度小于参数$c$的个数,然后计算最高位小于$A[m]$的数吗,然后一位一位下推,如果两个数的差值比1小,那么说明下面就不能这样做了,因为不是windy数了。

那我们来看代码

 

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

using namespace std;

int f[12][10];
// f[i,j] 表示 长度为i,最高位为j的windy数个数。 

// 计算(0,a)范围内的windy数个数 
int js(int a) {
	int m=0,A[20];
	int tmp=a;
	while(tmp) {
		A[m++]=tmp%10;
		tmp/=10;
	}
	int ret=0;
	for(int i=1;i<m;++i) 
		for (int j=1;j<10;++j)
			ret+=f[i][j];
	for (int i=1;i<A[m-1];++i) ret+=f[m][i];
	for (int i=m-1;i>=1;--i) {
		for (int j=0;j<A[i-1];++j) 
			if(abs(j-A[i])>1) ret+=f[i][j];
		if(abs(A[i]-A[i-1])<=1) break;
	}
	return ret;
}
int main() {
	memset(f,0,sizeof(f));
	for (int i=0;i<10;++i) f[1][i]=1;
	for (int i=2;i<=11;++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];
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d\n",js(b+1)-js(a));
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter