Category: 动态规划

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1833

仍然是数位dp

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 20;

LL f[MAXN][MAXN][MAXN],ans[MAXN],p[MAXN];

inline void prework(){
	p[0] = 1; p[1] = 10; 
	for (int i=2;i<=12;i++) p[i] = p[i-1]*10;
	for (int i=0;i<=9;i++) f[1][i][i] = 1;
	for (int k=2;k<=12;k++) {
		for (int i=0;i<=9;i++) {
			for (int j=0;j<=9;j++) {
				for (int h=0;h<=9;h++) {
					f[k][i][h] += f[k-1][j][h];
				}
			}
			f[k][i][i] += p[k-1];
		}
	}
}

inline void cal(LL w, int t){
	if (!w) return;
	else {
		int tot = 0, arr[20]; LL tmp = w;
		memset(arr,0,sizeof(arr));
		while (w) arr[++tot] = w % 10, w /= 10;
	
		for (int i=tot-1;i;i--) for (int j=1;j<=9;j++) 
			for (int k=0;k<=9;k++) ans[k] += f[i][j][k]*t;
		for (int i=tot;i;i--) {
			for (int j=(i==tot?1:0);j<=arr[i]-(i==1?0:1);j++) 
				for (int k=0;k<=9;k++) ans[k] += f[i][j][k]*t;
			if (i>1) ans[arr[i]] += (tmp % p[i-1] + 1)*t;
		}
	}
}

int main(){
	prework();
	LL a,b; cin>>a>>b;
	cal(b,1); 
	cal(a-1,-1);
	for (int i=0;i<9;i++) printf("%lld ", ans[i]);
	printf("%lld",ans[9]);
	return 0;
} 

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3555

数位dp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;

const int MAXN = 30;

LL f[MAXN][MAXN][2];

inline LL read(){
	char c=getchar(); LL ret = 0;
	while (c<'0'||c>'9') c = getchar();
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret;
}

inline void prework(){
	for (int i=0;i<=9;i++) f[1][i][0] = 1;
	for (int k=2,tmp=0;k<=28;k++) {
		for (int i=0;i<=9;i++) {
			for (int j=0;j<=9;j++) {
				if (i == 4 && j == 9) f[k][i][1] += f[k-1][j][0];
				else f[k][i][0] += f[k-1][j][0];
				f[k][i][1] += f[k-1][j][1];
			}
		}
	}
}

inline LL cal(LL w){
	if (!w) return 0;
	else { 
		int tot = 0, arr[20]; LL ret = 0, tmp = w, t2;
		memset(arr,0,sizeof(arr));
		while (w) arr[++tot] = w % 10, w /= 10;
	
		for (int i=1;i<tot;i++) for (int j=1;j<=9;j++) ret += f[i][j][1];
		for (int i=1;i<arr[tot];i++) ret += f[tot][i][1];
		for (int i=tot-1;i;i--){
			for (int j=0;j<arr[i];j++) ret += f[i][j][1];
			if (arr[i+1] == 4 && arr[i] == 9) {
				ret += tmp%(LL)(pow(10,i-1)+0.1)+1;
				break;
			}
		}
		return ret;
	}
}

int main(){
	prework();
	int T; T = read();
	while (T--) {
		LL a=read();
		cout<<cal(a)<<endl;
	}
	return 0;
} 

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1026

数位DP

#include<iostream>
#include<cstdio>
#include<cstring>
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 20;

int f[MAXN][MAXN],a,b;

inline void prework(){
	for (int i=0;i<=9;i++) f[1][i] = 1;
	for (int k=2;k<=10;k++) {
		for (int i=0;i<=9;i++) {
			for (int j=i+2;j<=9;j++) f[k][i] += f[k-1][j];
			for (int j=i-2;j>=0;j--) f[k][i] += f[k-1][j];
		}
	}
}

inline int cal(int w){
	int tot=0,arr[MAXN],ret=0;
	memset(arr,0,sizeof(arr));
	while (w) arr[++tot] = w % 10, w /= 10;
	
	for (int i=1;i<tot;i++) for (int j=1;j<=9;j++) ret += f[i][j];
	for (int i=1;i<arr[tot];i++) ret += f[tot][i];
	for (int i=tot-1;i>0;i--) {
		for (int j=0;j<=arr[i]-(i==1?0:1);j++)if (abs(j-arr[i+1]) >= 2) ret += f[i][j];
		if (abs(arr[i]-arr[i+1]) < 2) break;
	}
	return ret+(tot==1);
}

int main(){
	prework();
	scanf("%d%d",&a,&b); 
	printf("%d",cal(b)-cal(a-1));
	return 0;
}