HDU 2089 不要62(数位dp模板题)
2024-10-16 15:25:24
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 ;
}
最新文章
- J. Bottles 二维费用背包问题
- node-webkit教程(8)Platform Service之Clipboard
- Python3基础 逻辑与 and
- ios 缓存策略
- 修改ssh服务的默认端口
- SendMessage、PostMessage原理
- 一句话美化你的下拉框之jQuery.selectMM插件
- python实现散列表的链表法
- SFTP环境搭建及客户代码调用公共方法封装
- win10下安装PHP_CodeSniffer 检查编码规范
- JAVA图书管理系统汇总共27个
- Impala Apache Hadoop 安装方法
- python语法_字符串拼接
- 【转】Linux常用命令
- java容器类---概述
- pyoj61 双线DP
- request.getParameterMap()获得Map中的数据
- LeetCode——Implement Queue using Stacks
- Hadoop运维手记
- 在MarkDown中插入数学公式对照表(持续更新)
热门文章
- ubuntu 安装ftp,配置,和java调用
- vertx 从Tcp服务端和客户端开始翻译
- Linux中Kill掉进程的10种方法
- 二进制协议 vs 文本协议
- docker命令及操作
- 浅谈Android View滑动冲突
- GreenPlum安装greenplum-cc-web监控
- Vue项目使用AES做加密
- Root :: AOAPC I: Beginning Algorithm Contests (Rujia Liu) Volume 5. Dynamic Programming
- C++矩阵库 Eigen 快速入门