本文主要是介绍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;
}这篇关于MmMm数（dp,记忆搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
