企业管理网站的来历,wordpress歌词插件,品牌营销增长公司哪家好,新网域名备案数位动态规划 数位动态规划是求解一个大区间[L, R]中间满足条件Q的所有数字的个数#xff08;或者和#xff0c;或其他#xff09;的一种方法。它通过分析每一位上的数字#xff0c;一般用 dp[len][digit][...] 来表示状态“len位长的数字#xff0c;最高位数字为digi… 数位动态规划 数位动态规划是求解一个大区间[L, R]中间满足条件Q的所有数字的个数或者和或其他的一种方法。它通过分析每一位上的数字一般用 dp[len][digit][...] 来表示状态“len位长的数字最高位数字为digit所具有的xx特性”利用记忆化搜索保存中间结果从而加快求解速度。 通过求 f(n) 从0到n中满足条件Q的数字的个数则所求的结果为 f(R) - f(L-1). 大多数数位dp都可以用一个DFS函数来进行记忆化搜索 //len数字的位数digit最高位的值end_flag 表示digit是否是第len位从低位向高位数个位为第1位 的范围边界
int Dfs(int len, int digit, bool end_flag){//超出边界if (len 0 || digit 9 || digit 0)return 0;//记忆化搜索如果之前已经求出来了则返回。注意这里要求 end_flag为falseif (!end_flag dp[len][digit] ! -1)return dp[len][digit];// 最简单情况看数字是否满足要求if (len 1)return dp[len][digit] xxx;//如果当前位是边界数字N对应位的最大值则下一位的范围只能从0到边界数字N的下一位的最大值。否则为0 到 9int end end_flag ? bits[len - 2] : 9; int ans 0;for (int i 0; i end; i){ans Dfs(len - 1, i, end_flag (iend));}if (!end_flag) //digit不是第len位的最高范围则可以将结果缓存dp[len][digit] ans;return ans;
}题目大意 给定一个区间[L, R]求区间内满足条件“数位上不含有4且不含有6262必须连续”的数字的个数。 分析 直接套用模板 实现 #includeiostream
#includestdio.h
using namespace std;
int dp[9][10];
int bits[8];//用dfs进行记忆化搜索 dp[len][digit] 表示 len位数字最高位为digit满足条件的个数. 这里对数字范围没有限制
//搜索的时候若要进行记忆化需要 dp[len][digit]的结果对数字范围没有限制因此需要判断 end_flag来决定是否进行记忆。//len数字的位数digit最高位的值end_flag 表示digit是否是第len位从低位向高位数个位为第1位 的范围边界
int Dfs(int len, int digit, bool end_flag){//超出边界if (len 0 || digit 9 || digit 0)return 0;//记忆化搜索如果之前已经求出来了则返回。注意这里要求 end_flag为falseif (!end_flag dp[len][digit] ! -1)return dp[len][digit];// 最简单情况看数字是否满足要求if (len 1)return dp[len][digit] (digit ! 4);if (digit 4)return dp[len][digit] 0;//如果当前位是边界数字N对应位的最大值则下一位的范围只能从0到边界数字N的下一位的最大值。否则为0 到 9int end end_flag ? bits[len - 2] : 9; int ans 0;for (int i 0; i end; i){if (!(digit 6 i 2)) //除去 62连续的情况ans Dfs(len - 1, i, end_flag (iend));}if (!end_flag) //digit不是第len位的最高范围则可以将结果缓存dp[len][digit] ans;return ans;
}//将数字n的各个位上的范围求出来保存到bits数组中返回数字n的长度
int Init(int n){ memset(bits, 0, sizeof(bits));int k 0;while (n){bits[k] n % 10;n / 10;}return k;
}int Solve(int n){ int len Init(n); //数字长度为len则为了避免首位遍历从0到bits[len-1]给数字增加一个前导0。//len 1位首位为0且0是最高位的边界int ans Dfs(len 1, 0, true);return ans;
}
int main(){int m, n;memset(dp, -1, sizeof(dp));while (scanf(%d %d, m, n)){if (m 0 n 0)break; int ret1 Solve(m-1);int ret2 Solve(n);int ret ret2 - ret1;printf(%d\n, ret);}return 0;
}转载于:https://www.cnblogs.com/gtarcoder/p/5463451.html
