数位DP
数位DP
所谓数位DP，就是把一个数按照k进制数的每一个位展开，在把每一位的信息作为状态来推出答案。
比如：12345这个数在十进制下可拆为1、2、3、4、5，个位可以推十位，十位可以推百位，以此类推。推状态的方法有很多，一般来说第一反应就是像普通dp一样从前往后推，但是由于思维难度较高而且写起来难度较大，所以推荐递归写法，也就是记忆话搜索的写法。
以HDU2089 不要62为例。
统计l,r区间内不含62,4的数字个数。
l~r区间符合条件的数字没有普遍的规律，状态数目过多不好做DP。但是1~x一段连续的区间在枚举数字时有大量重复状出现，利用记忆化搜索做DP。
一、首先将问题拆分成两部分，也就是1~r区间内符合条件数字的数目减去1~(l-1)区间内符合条件数字的数目。
ans=solve(r)-solve(l-1);
二、将输入的边界x转化为k进制存入数组备用。
int solve(int x)
{
int pos=0;
while(x)
{
a[pos++]=x%10;
x/=10;
}
return dfs(pos-1,-1,0,true);
} 三、安位枚举所有的数字，过程中发现状态已经搜索过，就可以直接返回答案（记忆化）
int dfs(int pos,int pre,int sta,bool limit)//pos当前数位,pre上一个数字,sta：pre是否为6，limit代表是否有至少有一个高位小于数位限制，如果小于的话，后面所有数位均无限制条件。
{
if(pos==-1)return 1; //搜索到最后一位时，就说明找到了一个符合条件数
if(!limit&&dp[pos][sta]!=-1)return dp[pos][sta];//非limit表示后面的数位无特殊限制，这里产生了大量重复子问题，而limit条件下后面每一位都认为是特殊的，不会被重复枚举，记忆化无用。
int up=limit?a[pos]:9; //limit条件下对当前位增加特殊限制
int temp=0; //计数
for(int i=0; i<=up; i++)
{
if(i==4)continue;
if(pre==6&&i==2)continue; //跳过非法状态。
temp+=dfs(pos-1,i,i==6,limit&&i==a[pos]); //记忆化递归
}
if(!limit)dp[pos][sta]=temp;
return temp;
} 整体代码
#include<bits/stdc++.h>
using namespace std;
int dp[20][2],a[20];
int n,m;
int dfs(int pos,int pre,int sta,bool limit)
{
if(pos==-1)return 1;
if(!limit&&dp[pos][sta]!=-1)return dp[pos][sta];
int up=limit?a[pos]:9;
int temp=0;
for(int i=0; i<=up; i++)
{
if(i==4)continue;
if(pre==6&&i==2)continue;
temp+=dfs(pos-1,i,i==6,limit&&i==a[pos]);
}
if(!limit)dp[pos][sta]=temp;
return temp;
}
int solve(int x)
{
int pos=0;
while(x)
{
a[pos++]=x%10;
x/=10;
}
return dfs(pos-1,-1,0,true);
}
int main()
{
int l,r;
while(~scanf("%d%d",&l,&r)&&l+r)
{
memset(dp,-1,sizeof(dp));
printf("%d\n",solve(r)-solve(l-1));
}
return 0;
} 
查看19道真题和解析
