局域网创建网站,现在外地人能进深圳吗,公司网站建设合同,主流建站cms数位dp,主要用来解决统计满足某类特殊关系或有某些特点的区间内的数的个数#xff0c;它是按位来进行计数统计的#xff0c;可以保存子状态#xff0c;速度较快。数位dp做多了后#xff0c;套路基本上都差不多#xff0c;关键把要保存的状态给抽象出来#xff0c;保存下来…数位dp,主要用来解决统计满足某类特殊关系或有某些特点的区间内的数的个数它是按位来进行计数统计的可以保存子状态速度较快。数位dp做多了后套路基本上都差不多关键把要保存的状态给抽象出来保存下来。 简介 顾名思义所谓的数位DP就是按照数字的个十百千……位数进行的DP。数位DP的题目有着非常明显的性质 询问[l,r]的区间内有多少的数字满足某个性质 做法根据前缀和的思想求出[0,l-1]和[0,r]中满足性质的数的个数然后相减即可。 算法核心 关于数位DP貌似写法还是比较多的有递归的也有非递归的。下面学习一下较好理解可拓展性较高的递归写法。 LL dfs(int x,int pre,int bo,int limit);一般需要以上参数当然具体情况具体分析。 x表示当前的数位一般都是从高位到低位pre表示前一位的数字bo可以表示一些附加条件是否有前项0是否包含49是否当前已经符合条件……limit这个很重要它表示当前数位是否受到上一位的限制比较抽象举例说明如果上限是135前两位已经是1和3了现在到了个位个位只能是5以下的数字注如果当前受限不能够记忆化也不能返回记忆化的结果为了避免多次调用时 每次上限不同 而导致的错乱影响 例题HDU 3555 题意a到b中有多少个数字包含49 思路 dfs(x,pre,bo,limit)表示当前位置前一位的数字当前是否已经包含49以及是否有上界当然直接搜索肯定TLEf[x][pre][bo]记忆化即可。 #includeiostream
#includecstring
#includecstdio
#includecmath
#includealgorithm
using namespace std;
const int N 20;
#define LL long long
int dig[N];
LL f[N][10][2];
// 数位前一位数是否符合条件是否符合限制 [从高位到低位处理]
LL dfs(int x, int pre, int bo, int limit){if (x 0) return bo; // 已经枚举了最后一位if (!limit f[x][pre][bo] ! -1) return f[x][pre][bo]; // 记忆化dpint last limit ? dig[x] : 9; // 确定这一位的上限是多少LL re 0;for (int i 0; i last; i)re dfs(x - 1, i, bo || (pre 4 i 9), limit (i last));if (!limit) f[x][pre][bo] re; // 当前受限不能够记忆化也不能返回记忆化的结果return re;
}
LL solve(LL n){int len 0;while (n){dig[len] n % 10;n / 10;}return dfs(len - 1, 0, 0, 1);
}
int main(){memset(f, -1, sizeof(f));int T; scanf(%d, T);while (T--){LL n;cin n;cout solve(n) endl;}return 0;
} 转载于:https://www.cnblogs.com/demian/p/7442215.html
