uva11038_How Many O's?_数位DP
2024-08-31 22:13:50
问m~n之间的数中共有多少个0,过程稍稍麻烦了一些,半天的时间才搞定。
直接上码吧
/*************************************************************************
> File Name: 11038_数位DP.cpp
> Author: Chierush
> Mail: qinxiaojie1@gmail.com
> Created Time: 2013年06月16日 星期日 16时13分54秒
************************************************************************/ #include <iostream>
#include <cstring>
#include <cstdlib>
#include <set>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm> #define LL long long
#define LLU unsigned long long using namespace std; LL g(char *s)
{
LL ans=0;
for (int i=1;i<strlen(s);++i)
ans=ans*10+s[i]-'0';
return ++ans;
} LL f[12],Count[12],sum[12],sbit[12];
char s[12]; LL dp(LL n)
{
if (n<0) return 0;
if (n<10) return 1;
LL ans=0;
sprintf(s,"%lld",n);
ans+=sum[strlen(s)-1]+(s[0]-'1')*(sum[strlen(s)-1]+sbit[strlen(s)-1]);
//printf("---%lld\n",ans);
for (int i=1;i<strlen(s)-1;++i)
if (s[i]>'0')
{
ans+=(sum[strlen(s)-i-1]+sbit[strlen(s)-i-1])*(s[i]-'1');
ans+=Count[strlen(s)-i-1]+sum[strlen(s)-i-1]+sbit[strlen(s)-i-1];
}
else
ans+=g(s+i);
return ++ans;
} int main()
{
Count[1]=10;
for (int i=2;i<=10;++i)
Count[i]=Count[i-1]*10;
for (int i=2;i<=10;++i)
sbit[i]=Count[i-1]+sbit[i-1];
sum[1]=f[1]=1;
for (int i=2;i<=10;++i)
f[i]=9*(sum[i-1]+sbit[i-1]),sum[i]=sum[i-1]+f[i];
LL n,m;
//printf("%lld\n",dp(500));
while (scanf("%lld%lld",&m,&n) && m>=0)
printf("%lld\n",dp(n)-dp(m-1));
return 0;
}
最新文章
- DatePicker及其监听
- setObject()用法
- jelq
- python基础——装饰器
- Sublime Text对Python代码加注释的快捷键
- 1.1Linux 系统简介(学习过程)
- nodejs技术面试问题整理
- [linux] linux 破解版confluence安装
- C++学习笔记:List容器
- 在QTableView中使用各种自定义委托
- video视频铺满
- 基于python的统计公报关键数据爬取
- shell版的nginx安装
- LoadRunner-参数化(参数间关联)
- iOS UI-创建空项目
- php session阻塞页面分析及优化 (session_write_close session_commit使用)
- 2018.08.30 bzoj4318: OSU!(期望dp)
- fork函数和vfork函数的区别--19
- 团体程序设计天梯赛L1-019	谁先倒 2017-03-22 17:35 33人阅读 评论(0) 收藏
- dede 后台登录以后一片空白