[poj 3252]数位dp前导0的处理
2024-09-07 19:40:02
通过这个题对于数位dp中前导0的处理有了新的认识。
题目链接:http://poj.org/problem?id=3252
//http://poj.org/problem?id=3252 #include<cstdio>
#include<cstring>
using namespace std; int b[];
int dp[][][]; int dfs(int pos,int preok,int more,int pre0)
{
if (pos==-) return more==?:;
if (preok && dp[pos][more+][pre0]!=-) return dp[pos][more+][pre0];
int up=preok?:b[pos];
int ans=;
for (int i=;i<=up;i++)
{
if (i<b[pos]||preok) ans+=dfs(pos-,,more+(i==?:pre0-),pre0&&!i);
else ans+=dfs(pos-,,more+(i==?:pre0-),pre0&&!i);
}
if (preok) dp[pos][more+][pre0]=ans;
//printf("pos=%d preok=%d more=%d pre0=%d ans=%d\n",pos,preok,more,pre0,ans);
return ans;
} int solve(int n)
{
if (n<) return ;
int cnt=;
int now=n;
do{
b[cnt]=now%;
now/=;
cnt++;
}while (now);
int ans=;
for (int i=;i<=cnt;i++)
ans+=dfs(cnt-,,i,);
return ans;
} int main()
{
int n,m;
memset(dp,-,sizeof(dp));
while (~scanf("%d%d",&n,&m))
{
printf("%d\n",solve(m)-solve(n-));
}
return ;
}
最新文章
- 趣味C程序-HelloWord
- angularjs的$filter使用
- java基础知识复习
- 选择哪种方式进行SharePoint的备份
- hdu 4585 map **
- vilte/vowifi
- @media screen解决移动web开发的多分辨率问题
- Delphi-CompareStr 函数
- Android的JNI开发
- 单机使用tungsten 同步mysql数据到mongodb
- Nginx 搭建反向代理服务器过程详解
- tableview cell添加3D动画
- HTML第一课
- cisco linksys ea3500 刷机 openwrt
- hadoop集群崩溃,因为tmp下/tmp/hadoop-hadoop/dfs/name文件误删除
- SpringBoot系列: 制作Docker镜像的全过程
- 爬虫(五)requests模块2
- 大数据技术 - 通俗理解MapReduce之WordCount(二)
- Servlet注释与部署描述符
- oracle 查出一个表中字段值出现次数大于2的所有记录