博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
数位DP模板
阅读量:5316 次
发布时间:2019-06-14

本文共 1025 字,大约阅读时间需要 3 分钟。

#include 
#include
#include
#include
using namespace std;int t;long long dp[19][19][2005];long long l, r;int digit[20];long long dfs(int len,...int if4..., bool limit){ if (len == 0) return 1; //个位 if (!limit && dp[len][...]) return dp[len][...]; //dp数组的内容应和dfs调用参数的内容相同,除了是否达到上限 long long cnt = 0; int up_bound = (limit ? digit[len] : 9); for (int i = 0; i <= up_bound; i++) { if(...) continue; //剪枝 ...; cnt += dfs(len-1, ..., limit && i == up_bound); } if (!limit) //完整状态 dp[len][...] = cnt; return cnt;}long long solve(long long x){ int k = 0; while (x) { digit[++k] = x % 10; x /= 10; } return dfs(k,...,1)}int main(){ memset(dp, 0, sizeof(dp)); scanf("%lld%lld", &l, &r); //有些题目其实并不需要用到long long printf("%lld\n", solve(r) - solve(l - 1)); //只有满足区间减法才能用 return 0;}

 

转载于:https://www.cnblogs.com/Roni-i/p/9425497.html

你可能感兴趣的文章
五月28学习笔记
查看>>
洛谷P1019 单词接龙
查看>>
c++学习笔记九
查看>>
输出最大值MXNet实现
查看>>
BFS HDOJ 2102 A计划
查看>>
SQL中的left outer join,inner join,right outer join用法 (左右内连接)
查看>>
Java研发方向如何准备BAT技术面试答案(上)
查看>>
saltstack 主题说明
查看>>
服务发现与健康监测框架Consul-DNS转发的应用
查看>>
IPC之——消息队列
查看>>
.Net FrameWork
查看>>
IOS多线程
查看>>
man:命令帮助使用手册
查看>>
进程共享变量#pragma data_seg用法
查看>>
supervisord的安装使用
查看>>
趣谈unicode,ansi,utf-8,unicode big endian这些编码有什么区别
查看>>
nowcoder OI 周赛 最后的晚餐(dinner) 解题报告
查看>>
javascript高级程序设计 学习笔记 第五章 上
查看>>
页面置换算法及例题
查看>>
Python基础学习总结__Day3
查看>>