SPOJ BALNUM Balanced Numbers（数位DP+状态压缩）题解

思路：

把0~9的状态用3进制表示，数据量3^10

代码：

#include<cstdio>

#include<map>

#include<set>

#include<queue>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

const int N = 500+5;

const int INF = 0x3f3f3f3f;

using namespace std;

int dp[22][60000];  //0 没出现，1 奇数，2 偶数

int dig[22];

int check(int sta){

    for(int i = 0;i <= 9;i++){

        int tmp = sta % 3;

        sta /= 3;

        if(i % 2 == 1 && tmp == 1) return 0;

        else if(i % 2 == 0 && tmp == 2) return 0;

    }

    return 1;

}

int news(int sta,int x){

    int num[10];

    for(int i = 0;i <= 9;i++){

        num[i] = sta % 3;

        sta /= 3;

    }

    int tmp = 0;

    if(num[x] == 0) num[x] = 1;

    else num[x] = 3 - num[x];

    for(int i = 9;i >= 0;i--){

        tmp = tmp*3 + num[i];

    }

    return tmp;

}

ll dfs(int pos,int sta,bool lead,bool limit){

    if(pos == -1) return check(sta);

    if(!limit && dp[pos][sta] != -1) return dp[pos][sta];

    int top = limit? dig[pos] : 9;

    ll ret = 0;

    for(int i = 0;i <= top;i++){

        int STA = news(sta,i);

        if(lead && i == 0) STA = 0;

        ret += dfs(pos - 1,STA,lead && i == 0,limit && i == top);

    }

    if(!limit) dp[pos][sta] = ret;

    return ret;

}

ll solve(ll x){

    int pos = 0;

    if(x == 0) return 1;

    while(x){

        dig[pos++] = x % 10;

        x /= 10;

    }

    return dfs(pos - 1,0,true,true);

}

int main(){

    int T;

    ll a,b;

    scanf("%d",&T);

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

    while(T--){

        scanf("%lld%lld",&a,&b);

        printf("%lld\n",solve(b) - solve(a - 1));

    }

    return 0;

}

巴特西

SPOJ BALNUM Balanced Numbers（数位DP+状态压缩）题解

最新文章

热门文章