UESTC1307 windy数 数位DP

windy定义了一种windy数。 不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

dp[i][j],代表j开头的i位数字，跟前面几道 差不多，然后枚举递推各个数位上数字关系，感觉 比前面做的还简单，大差不差 ，因为没有前导0，所以从高位开始搞起比较方便

总是做算法，不如来个陶冶情操的文章一篇： http://www.sanwen.net/subject/3628849/

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;

int dp[100 + 5][100 + 5];
int sum[100 + 5];
int num[100 + 5];

void init() {
	int i,j,k;
	for(i=0;i<10;i++) 
		dp[i][1] = dp[i][0] = 1;
	sum[1] = 10;
	for(j=2;j<=10;j++)  {
		sum[j] = sum[j - 1];
		for(i=0;i<10;i++) {
			for(k=0;k<10;k++)
				if(abs(i - k) > 1)
					dp[i][j] += dp[k][j - 1];
			if(i)
				sum[j] += dp[i][j];
		}
	}
}

int cal(int x) {
	memset(num,0,sizeof(num));
	if(x == 0) return 0;
	if(x < 10) return x;
	int cnt = 0;
	while(x) {
		num[cnt++] = x%10;
		x /= 10;
	}
	for(int i=0;i<cnt/2;i++) {
		int tmp = num[i];
		num[i] = num[cnt - i - 1];
		num[cnt - i - 1] = tmp;
	}
	int ans = 0;
	for(int i=0;i<cnt;i++) {
		if(i == cnt - 1) {
			for(int j =0;j<=num[i];j++)
				if(abs(num[i-1] - j) > 1)
					ans += dp[j][cnt - i];
		}
		else if(i) {
			for(int j=0;j<num[i];j++) 
				if(abs(num[i-1] - j) > 1)
					ans += dp[j][cnt - i];
			if(abs(num[i] - num[i-1]) < 2)
				return ans - 1;
		}
		else {
			ans = sum[cnt - 1];
			for(int j=1;j<num[0];j++) 
				ans += dp[j][cnt];
		}
	}
	return ans - 1;
}

int main() {
	init();
	int a,b;
	while(scanf("%d %d",&a,&b) == 2) {
		printf("%d\n",cal(b) - cal(a-1));
	}
	return EXIT_SUCCESS;
}

UESTC1307 windy数 数位DP,布布扣,bubuko.com

UESTC1307 windy数 数位DP

原文：http://blog.csdn.net/yitiaodacaidog/article/details/22217057