首页 > 代码库 > 数位DP模板
数位DP模板
解释一下:dp数组只保存!limit和!first的状态
dp数组保存的是,当前位确定后,之后的数字没有限制的结果,显然当limit或者first时候是不适合的。
first的时候是没必要记录的,因为到当前状态只有一条路径(当前位前边全零)
limit的时候也是没必要记录的,因为到当前状态只有一条路径(当前位前边和待求得串相同)
const int MAX_DIGITS, MAX_STATUS; LL f[MAX_DIGITS][MAX_STATUS], bits[MAX_DIGITS]; LL dfs(int position, int status, bool limit, bool first) { if (position == -1) return s == target_status; if (!limit && !first && ~f[position][status]) return f[position][status]; int u = limit ? bits[position] : MAX_BITS; LL ret = 0; for (int i = 0; i <= u; i++) { ret += dfs(position - 1, next_status(status, i), limit && i == u, first && !i); } return limit || first ? ret : f[pos][status] = ret; } LL calc(LL n) { CLR(f, -1); int len = 0; while (n) { bits[len++] = n % 10; n /= 10; } return dfs(len - 1, 0, true, true); } int main() { //freopen("0.txt", "r", stdin); LL a, b; while (cin >> a >> b) cout << calc(b) - calc(a - 1) << endl; return 0; }
数位DP模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。