博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ-1833(数位DP)
阅读量:5051 次
发布时间:2019-06-12

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

#include 
using namespace std;typedef long long ll;ll a,b;int k[20];ll dp[20][10];ll sum[20];ll ddfs(int pos,int lead,bool limit){ if(pos == -1)return 1; if(!limit && !lead && sum[pos])return sum[pos]; int up = limit ? k[pos]:9; ll res = 0; for(int i=0;i<=up;i++){ res += ddfs(pos-1,lead && i==0,limit && i == k[pos]); } if(!limit && !lead)sum[pos] = res; return res;} ll dfs(int pos,int x,bool lead,bool limit){ if(pos == -1)return lead; if(!limit && !lead && dp[pos][x])return dp[pos][x]; int up = limit ? k[pos] : 9; ll res = 0; for(int i=0;i<=up;i++){ if(lead){ if(i == 0){ res += dfs(pos-1,x,lead,false);continue; } } if(i == x){ res += ddfs(pos-1,false,limit && i == k[pos]); res += dfs(pos-1,x,false,limit && i == k[pos]); } else res += dfs(pos-1,x,false,limit && i == k[pos]); } if(!limit && !lead)dp[pos][x] = res; return res;}ll solve(ll x,int z){ int pos = 0; while(x){ k[pos++] = x%10; x/=10; } return dfs(pos-1,z,true,true);}int main(){ scanf("%lld%lld",&a,&b); for(int i=0;i<=9;i++){ printf("%lld ",solve(b,i) - solve(a-1,i)); } //printf("%lld\n",dp[0][1]); puts(""); return 0;}

转载于:https://www.cnblogs.com/1625--H/p/10876844.html

你可能感兴趣的文章
Equal Sides Of An Array
查看>>
CentOS笔记-用户和用户组管理
查看>>
Mongodb 基本命令
查看>>
Qt中QTableView中加入Check列实现
查看>>
“富豪相亲大会”究竟迷失了什么?
查看>>
控制文件的备份与恢复
查看>>
返回代码hdu 2054 A==B?
查看>>
Flink独立集群1
查看>>
iOS 8 地图
查看>>
20165235 第八周课下补做
查看>>
[leetcode] 1. Two Sum
查看>>
iOS 日常工作之常用宏定义大全
查看>>
PHP的SQL注入技术实现以及预防措施
查看>>
MVC Razor
查看>>
软件目录结构规范
查看>>
Windbg调试Sql Server 进程
查看>>
linux调度器系列
查看>>
mysqladmin
查看>>
解决 No Entity Framework provider found for the ADO.NET provider
查看>>
SVN服务器搭建和使用(三)(转载)
查看>>