POJ 3286 How many 0's（数位DP模板）

题目大意：

输入n,m，求[n,m]的所有数字中，0出现的总数是多少，前导零不算。

解题思路：

模板题，设dp[pos][num]，pos为数位，num为当前0的数目，然后套数位DP模板即可。

还有之前的一些思考：

关于数位DP求0时，dp下标记录num有什么作用,num不是与后面的0的个数无关吗？
是的，在(!limit&&!lead)的情况下，前面有多少0是不影响后面可以出现多少0的。
但是，比如说dp[pos][num]吧,dp[1][0]=1,但是dp[1][1]=11，这样应该有点明白了吧，
虽然后面有多少0不影响，但是记忆化的结果加上了前面的0的数量num，就像后者多余的10个0都是num贡献的,

说明num是会影响记忆化结果的，所以num需要当做下标记录下来。

代码

 #include<cstdio>

 #include<cmath>

 #include<cctype>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #include<set>

 #include<map>

 #include<stack>

 #include<string>

 #define lc(a) (a<<1)

 #define rc(a) (a<<1|1)

 #define MID(a,b) ((a+b)>>1)

 #define fin(name)  freopen(name,"r",stdin)

 #define fout(name) freopen(name,"w",stdout)

 #define clr(arr,val) memset(arr,val,sizeof(arr))

 #define _for(i,start,end) for(int i=start;i<=end;i++)

 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

 using namespace std;

 typedef long long LL;

 const int N=5e6+;

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 LL top[];

 LL dp[][];

 LL dfs(bool limit,bool lead,LL pos,LL num){

     if(pos==-)

         return num;

     if(!limit&&!lead&&dp[pos][num]!=-) return dp[pos][num];

     LL up=limit?top[pos]:;

     LL ans=;

     for(int i=;i<=up;i++){

         ans+=dfs(limit&&i==up,lead&&i==,pos-,num+(i==&&!lead));

     }

     if(!lead&&!limit) dp[pos][num]=ans;

     return ans;

 }

 LL solve(LL x){

     memset(dp,-,sizeof(dp));

     int cnt=-;

     while(x){

         top[++cnt]=x%;

         x/=;

     }

     return dfs(,,cnt,);

 }

 int main(){

     FAST_IO;

     LL l,r;

     while(cin>>l>>r){

         if(l==-&&r==-)

             break;

         LL ans=;

         if(l==) l++,ans++;

         ans+=solve(r)-solve(l-);

         cout<<ans<<endl;

     }

     return ;

 }

秒客网

POJ 3286 How many 0's（数位DP模板）

相关文章