数位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\n" , 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 ;

}

巴特西

数位dp（不要62）

最新文章

热门文章