保定网站seo,个人网站作品欣赏,爱南宁app下载官网中小学,啦啦啦中文免费视频高清观看题目
题目链接#xff1a; https://www.luogu.com.cn/problem/P4124
分析
给定两个长度为11位的数字#xff0c;代表两个区间 [L,R] 需要编写程序来计算出#xff0c;这两个区间内满足要求的数字个数。这样的题一般来说就是数位dp题。首先我们可以根据容斥原理 [0,R]中满…题目
题目链接 https://www.luogu.com.cn/problem/P4124
分析
给定两个长度为11位的数字代表两个区间 [L,R] 需要编写程序来计算出这两个区间内满足要求的数字个数。这样的题一般来说就是数位dp题。首先我们可以根据容斥原理 [0,R]中满足要求的个数 - [0,L-1]中满足要求的个数 来计算出 [L,R] 这个区间中满足要求数字的数量。
但是由于给定的数字范围很大超过了int与long类型的范围只能用字符串存储那么字符串的加减计算就变得很麻烦了。那么可以这样计算 [0,R]-[0,L] 最后再特判一下 L 串是否符合要求符合要求的话最后的答案再1。
根据题目要求我们需要使用两个变量来记录前两个位置上的数用来判断是否符合条件还需要一个变量来记录当前数字是否满足要求还有使用一个变量来记录当前数字是否出现过4与8。
然后就是套用数位dp的模板了。 code
package dp.数位dp;import java.util.*;public class Main {static final int N 12;static final int M (1 11);static long[][][][][] memo new long[N][N][N][2][M];public static void main(String[] args) {Scanner in new Scanner(System.in);// 由于数字位数太大那么只能用字符串读取再转成字符数组char[] l in.next().toCharArray();char[] r in.next().toCharArray();reset(r.length);long ans dfs(r, 0, 10, 10, false, true, 0);reset(l.length);ans - dfs(l, 0, 10, 10, false, true, 0);if (check(l)) {ans;}System.out.println(ans);}/** chs 从高到底存储着数字的每一个数位* i 当前数位下标* pp 表示当前数位前一位的前一位数字* p 表示当前数位前一位的数字* flag 表示当前数字中是否出现过3个相邻且相等的数字* isLimit 表示构造当前位数字是否受限制* status 用二进制位来判断当前数字中是否同时出现过4与8* */public static long dfs(char[] chs, int i, int pp, int p, boolean flag, boolean isLimit, int status) {if (i chs.length) {return flag ? 1 : 0;}if (!isLimit memo[i][pp][p][flag ? 1 : 0][status] ! -1) {return memo[i][pp][p][flag ? 1 : 0][status];}long ans 0;int up isLimit ? chs[i] - 0 : 9; // 获取构造当前数字的上限// 无前导零for (int d (i 0) ? 1 : 0; d up; d) {// 不能同时出现4或8if ((d 4 ((status 8) 1) ! 0) || (d 8 ((status 4) 1) ! 0)) {continue;}ans dfs(chs, i 1, p, d, flag || (pp p d p), isLimit d up, status | (1 d));}if (!isLimit) {memo[i][pp][p][flag ? 1 : 0][status] ans;}return ans;}// 判断一个数字是否符合条件public static boolean check(char[] chs) {if(chs[0] 0) { return false; }char pp x, p x;boolean flagfalse,cnt4 false, cnt8 false;for (char ch : chs) {if (ch 4) {cnt4 true;} else if (ch 8) {cnt8 true;}if (cnt4 cnt8) {return false;}if (pp p p ch) {flagtrue;}pp p;p ch;}return !(cnt4 cnt8) flag;}public static void reset(int n) {for (int i 0; i n; i) {for (int j 0; j memo[i].length; j) {for (int k 0; k memo[i][j].length; k) {for (int u 0; u memo[i][j][k].length; u) {Arrays.fill(memo[i][j][k][u], -1);}}}}}
}
提交结果
