MmMm数（dp,记忆搜索）

Problem - 1274 (nefu.edu.cn)

Problem:1274

Time Limit:2000ms

Memory Limit:65535K

Description

什么是MmMm数，就是递增或递减的数。 
例如 112233, 123,而312这种就不算;
现在给你两个数，L,R,问在[L,R]中有多少个MmMm数。

Input

先输入一个数T，表示T组数据。(T<=100000)
然后T行，每行两个数L，R；(1<=L<=R<=1e9)

Output

  输出T组结果。

Sample Input

2
1 100
200 300

Sample Output

100
42

Hint

解析：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
using namespace std;
typedef long long LL;
int L, R;
int f[22], dp[22][12][4];
int ar[22];

LL dfs(int p, int u, int lis, int flg) {
	if (p <= 1)return 1;
	if (dp[p][u][lis] != -1 && !flg)return dp[p][u][lis];
	int num;
	LL ans = 0;
	num = flg ? ar[p - 1] : 9;
	for (int i = 0; i <= num; i++) {
		int flg2 = 0;
		if (i == num && flg)flg2 = 1;
		if (i == u && lis == 0)ans += dfs(p - 1, i, 0, flg2);
		if (i >= u && lis == 1)ans += dfs(p - 1, i, 1, flg2);
		if (i <= u && lis == 2)ans += dfs(p - 1, i, 2, flg2);
	}
	if (!flg)dp[p][u][lis] = ans;
	return ans;
}

LL solve(LL u) {
	LL ans = 0;
	int p = 0;
	while (u > 0) {
		ar[++p] = u % 10;
		u /= 10;
	}
	for (int i = 1; i < ar[p]; i++) {
		ans += dfs(p, i, 1, 0) + dfs(p, i, 2, 0) - dfs(p, i, 0, 0);
	}
	ans += dfs(p, ar[p], 1, 1) + dfs(p, ar[p], 2, 1) - dfs(p, ar[p], 0, 1);
	if (p == 0)
		return 0;
	return ans+f[p-1];
}

int main() {
	memset(dp, -1, sizeof dp);
	for (int i = 1,x=0; i < 19; i++) {
		x = x * 10 + 9;
		f[i] = solve(x);
	}
	int T;
	cin >> T;
	while (T--) {
		int l, r;
		scanf("%d%d", &l, & r);
		printf("%lld\n", solve(r) - solve(l - 1));
	}
	return 0;
}