数位dp（不要62）

http://acm.hdu.edu.cn/showproblem.php?pid=2089

题意：求区间内满足以下条件的数量

1、数位不能出现4，2、任意两相邻数位不能是62。

解法：数位dp【pos】【sta】表示第pos位为6和不是6两种状态的满足条件的数量。

//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdio.h>
#include <queue>
#include <stack>;
#include <map>
#include <set>
#include <ctype.h>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF  0x3f3f3f3f
#define mod 10
#define PI acos(-1)
using namespace std;
typedef long long ll ;
int a[10];
int dp[10][2];

int dfs(int pos , int pre , int sta , int limit)
{
    if(pos == -1) return 1;
    if(!limit && dp[pos][sta] != -1) return dp[pos][sta];
    int up = limit ? a[pos] : 9 ;
    int ans = 0 ;
    for(int i = 0 ; i <= up ; i++)
    {
        if(i == 4) continue ;
        if(pre == 6 && i == 2) continue ;
        ans += dfs(pos-1 , i , i == 6 , limit && a[pos] == i);
    }
    if(!limit) dp[pos][sta] = ans ;
    return ans ;
}

int solve(int x)
{
    int pos = 0 ;
    while(x)
    {
        a[pos++] = x % 10 ;
        x /= 10 ;
    }
    return dfs(pos-1 , 0 , 0 , 1);
}

int main()
{

    int n , m ;
    memset(dp , -1 , sizeof(dp));
    while(~scanf("%d%d" , &n , &m)&&n+m)
    {
        printf("%d
" , solve(m) - solve(n-1));
    }


    return 0;
}

2、暴力

//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdio.h>
#include <queue>
#include <stack>;
#include <map>
#include <set>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF  0x3f3f3f3f
#define mod 998244353
#define PI acos(-1)
using namespace std;
typedef long long ll ;
int a[10];
int vis[1000009];

void init()
{
    for(int i = 1 ; i <= 1000000 ; i++)
    {
        int l = 0 , t = i ;
        while(t)
        {
            a[l++] = t % 10;
            t /= 10 ;
        }
        for(int j = l - 1 ; j > 0 ; j--)
        {
            if(a[j] == 6 && a[j-1] == 2)
            {
                vis[i] = 1 ;
            }
            else if(a[j] == 4 || a[j-1] == 4)
            {
                vis[i] = 1 ;
            }
        }
    }
    vis[4] = 1 ;
}

int main()
{
    int n , m ;
    init();
    while(~scanf("%d%d" , &n, &m) && n + m)
    {
        int sum = 0 ;
        for(int i = n ; i <= m ; i++)
        {
            if(vis[i])
            {
                sum++ ;
            }
        }
        cout << (m - n + 1) - sum << endl ;
    }

    return 0 ;
}