首页 > 程序开发 > 综合编程 > 其他综合 >

ACdream 1064 完美数(数位dp)

2017-06-15

ACdream 1064 完美数(数位dp)。题意:在[L,R]的正整数区间内,要么包含3 要么包含 8 的不同的整数有多少个?

ACdream 1064 完美数(数位dp)。

题意:在[L,R]的正整数区间内,要么包含3 要么包含 8 的不同的整数有多少个?

题解:数位dp。
设:
dp[i][0]表示既没有3也没有8的,
dp[i][1]表示有3但是没有8的,
dp[i][2]表示有8但是没有3的。

代码:

/*
* this code is made by LzyRapx
* Problem: 1064
* Verdict: Accepted
* Submission Date: 2017-06-07 09:35:40
* Time: 188MS
* Memory: 1664KB
*/
#include 
using namespace std;
typedef long long ll;
//dp[i][0]表示既没有3也没有8的,
//dp[i][1]表示有3但是没有8的,
//dp[i][2]表示有8但是没有3的
int dp[11][4];
int digit[11];
int check(int s,int dig)
{
    if(dig==3)return s|1;
    if(dig==8)return s|2;
    return s;
}
int solve(int pos,int s,bool limit)
{
    if(pos==-1)return s==1 || s==2;
    if(!limit && dp[pos][s] != -1) return dp[pos][s];
    int res = 0;
    int ed = limit ? digit[pos]:9;
    for(int i=0;i<=ed;i++)
    {
        res += solve(pos-1,check(s,i),limit && i==ed);
    }
    if(!limit) dp[pos][s] = res;
    return res;
}
int cal(int x)
{
    int cnt = 0;
    while(x)
    {
        digit[cnt++] = x%10;
        x/=10;
    }
    return solve(cnt-1,0,1);
}
int main()
{
    int t ;
    cin>>t;
    memset(dp,-1,sizeof(dp));
    while(t--)
    {
        int l,r; 
        cin>>l>>r;
        cout<
        
   
相关文章
最新文章
热点推荐