数位DP和BZOJ1026题解

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

数位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;
}
admitcard-hallticket 说:
2023年4月28日 15:38

Board SSC or 10th Admit Card 2024, SSC Hall Ticket Board SSC, 10th Admit Card 2024. Board of Secondary and Higher Secondary Education conducts class 10th examination every year. admitcard-halltickets.in This year it will conduct the SSC exam in the month of April 2024. Every year thousands of candidates appear for it. They will be provided Board SSC Admit Card 2024 before the exam. You will be told all the information about it here.


登录 *


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