不要62 HDU - 2089

原题链接
考察:数位dp
思路:
??预处理时,不计入每位数字为4或首位为6,次位为2的数字.
??但是注意计算左分支的时候,我们是ans+=f[i+1][枚举的数字],如果枚举的数字为2,实际还需特判上一位.因为预处理首位数字为2时没有考虑上一位是什么.

Code

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 13;
int f[N][N],l,r;
void init()
{
    for(int i=0;i<=9;i++) f[1][i] = 1;
    f[1][4] = 0;
    for(int i=2;i<=12;i++)
      for(int j=0;j<10;j++)
        if(j!=4)
          for(int k=0;k<10;k++)
            if(j==6&&k==2) continue;
            else if(k==4) continue;
            else f[i][j] += f[i-1][k];
}
int dp(int n)
{
    if(!n) return 1;
    vector<int> v;
    while(n) v.push_back(n%10),n/=10;
    int ans = 0,last = 0;
    for(int i=v.size()-1;i>=0;i--)
    {
        int x = v[i];
        for(int j=0;j<x;j++)
         if(last==6&&j==2) continue;
		 else  ans+=f[i+1][j];
        if(x==4) break;
        if(last==6&&x==2) break;
        if(!i)  ans++;
        last = x;
    }
    return ans;
}
int main()
{
    init();
    while(scanf("%d%d",&l,&r)!=EOF&&(l+r))
        printf("%d\n",dp(r)-dp(l-1));
    return 0;
}

不要62 HDU - 2089

原文：https://www.cnblogs.com/newblg/p/14820887.html