开学之后完全没时间写博客....

HDU 2089 不要62(vjudge) 数位DP

思路:

题目给出区间[n,m] ,找出不含4或62的数的个数

用一个简单的差分:先求0~m+1的个数,再减去0~n的个数.

但问题依旧不简单,再次简化为求0~i位数中不含4或62的数的个数.

i= //0~9中
i= //0~99中
i= //0~999中
......
dp[i][] //0~i位数中的吉利数
dp[i][] //0~i位数中以2打头的吉利数
dp[i][] //0~i位数中的非吉利数(含4或62)

所以第i位数中的吉利数个数为:

dp[i][]=dp[i-1][]*-dp[i-][i]

第i位数中以2打头的幸运数个数为:

dp[i][]=dp[i-][]

第i位数中的非吉利数个数为:

dp[i][]=dp[i-][]*+dp[i-][]+dp[i-][]

同时初始值为:

dp[][]=;
dp[][]=;
dp[][]=;

AC码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int dp[][]; void INIT()
{
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<=;i++)
{
dp[i][]=dp[i-][]*-dp[i-][];//在吉利数首位补除了4的9个数,减去在2前补6的个数
dp[i][]=dp[i-][];//吉利数在首位补2
dp[i][]=dp[i-][]*+dp[i-][]+dp[i-][];//不吉利的情况
}
} int work(int x)
{
int d[],cnt=,temp=x;
while(temp)
{
d[++cnt]=temp%;
temp/=;
}
d[cnt+]=;
int flag=,ans=;
for(int i=cnt;i>;i--)
{
ans+=d[i]*dp[i-][];//用前一位所以不吉利数推出
if(flag) ans+=d[i]*dp[i-][];// 之前有不吉利数
else
{
if(d[i]>) ans+=dp[i-][];//4
if(d[i]>) ans+=dp[i-][];//6
if(d[i+]==&&d[i]>) ans+=dp[i][];//62
}
if(d[i]==||(d[i+]==&&d[i]==)) flag=;
}
return x-ans;//减去不吉利数的个数
} int main()
{
int m,n;
INIT();
while(~scanf("%d%d",&n,&m))
{
if(n==&&m==) break;
printf("%d\n",work(m+)-work(n));
}
return ;
}

2019-09-16 18:50:26

最新文章

  1. iOS 开发者账号到期续费流程
  2. 1.Android 视图及View绘制分析笔记之setContentView
  3. Spring实战 (第3版)——AOP
  4. PHP之MVC项目实战
  5. mysql 常用操作指令
  6. iOS开发--动画篇之layout动画深入
  7. ExtJS4.2学习(八)表格限制输入数据的类型(转)
  8. 定义Foo() 函数,弹出对话框提示当前选中的是第几个单选框
  9. Delphi 的接口机制——接口操作的编译器实现过程(2)
  10. 业务逻辑 : forex &amp; mlm
  11. Phaser文档访问不了,下载英文版文档到本地,已经共享在国内网站上面
  12. Python3.6下scrapy框架的安装
  13. 前端 SPA 单页应用数据统计解决方案 (ReactJS / VueJS)
  14. 如何在xlwt中编写多个列的单元格?
  15. implode() 数组元素组合函数
  16. js 时间戳转换为‘yyyy-MM-dd hh:mm’格式(es6语法)
  17. 正则表达式匹配URL或者网址
  18. laravel框架容器管理
  19. [翻译]EntityFramework Core 2.2 发布
  20. 用PE系统安装原版XP

热门文章

  1. neo4j 一些常用的CQL
  2. codeforces#1165 F2. Microtransactions (hard version) (二分+贪心)
  3. Linux 网络通信命令之 netstat
  4. HA 模式 Hadoop+ZooKeeper+Hbase启动顺序
  5. Elasticsearch删除数据之_delete_by_query
  6. 论一种基于JS技术的WEB前端动态生成框图的方法
  7. python 快速排序-代码示例
  8. DML语句
  9. C#可以直接调用的Win32API
  10. [ML] Machine Learning in the Common Infrastructure ecosystem