http://acm.hdu.edu.cn/showproblem.php?pid=2089

题意:
求区间内不包含4和连续62的数的个数。

思路:

简单的数位dp模板题。给大家推荐一个好的讲解博客。http://blog.csdn.net/mosquito_zm/article/details/75226543

 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn=+; int l,r;
int dp[maxn][];
int dig[]; int dfs(int pos, int pre, int state, int limit)
{
if(pos==-) return ;
if(!limit && dp[pos][state]!=-) return dp[pos][state];
int up=limit?dig[pos]:;
int tmp=;
for(int i=;i<=up;i++)
{
if(i==) continue;
if(pre== && i==) continue;
tmp+=dfs(pos-,i,i==,limit&&i==dig[pos]);
}
if(!limit) dp[pos][state]=tmp;
return tmp;
} int solve(int x)
{
int pos=;
while(x)
{
dig[pos++]=x%;
x/=;
}
return dfs(pos-,-,,);
} int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%d%d",&l,&r))
{
if(l== && r==) break;
memset(dp,-,sizeof(dp));
int ans=solve(r)-solve(l-);
cout<<ans<<endl;
}
return ;
}

最新文章

  1. J. Bottles 二维费用背包问题
  2. node-webkit教程(8)Platform Service之Clipboard
  3. Python3基础 逻辑与 and
  4. ios 缓存策略
  5. 修改ssh服务的默认端口
  6. SendMessage、PostMessage原理
  7. 一句话美化你的下拉框之jQuery.selectMM插件
  8. python实现散列表的链表法
  9. SFTP环境搭建及客户代码调用公共方法封装
  10. win10下安装PHP_CodeSniffer 检查编码规范
  11. JAVA图书管理系统汇总共27个
  12. Impala Apache Hadoop 安装方法
  13. python语法_字符串拼接
  14. 【转】Linux常用命令
  15. java容器类---概述
  16. pyoj61 双线DP
  17. request.getParameterMap()获得Map中的数据
  18. LeetCode——Implement Queue using Stacks
  19. Hadoop运维手记
  20. 在MarkDown中插入数学公式对照表(持续更新)

热门文章

  1. ubuntu 安装ftp,配置,和java调用
  2. vertx 从Tcp服务端和客户端开始翻译
  3. Linux中Kill掉进程的10种方法
  4. 二进制协议 vs 文本协议
  5. docker命令及操作
  6. 浅谈Android View滑动冲突
  7. GreenPlum安装greenplum-cc-web监控
  8. Vue项目使用AES做加密
  9. Root :: AOAPC I: Beginning Algorithm Contests (Rujia Liu) Volume 5. Dynamic Programming
  10. C++矩阵库 Eigen 快速入门