B-number HDU - 3652(디지털 dp+ 배제 원리)

2335 단어 디지털 dp용척 원리DP
A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13"and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.
Input
Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).
Output
Print each answer in a single line.
Sample Input 
13
100
200
1000

Sample Output 
1
1
2
2

 
제목: n보다 작은 것은 13으로 나눌 수 있고 13을 포함하는 수는 몇 개입니까
용척원리 n으로 13정제할 수 없는 것을 빼고 13을 포함하지 않는 것을 빼면 중간에 많이 빼면 13도 포함하지 않고 13정제할 수 없는 수를 더하면 답이다
코드는 다음과 같습니다.
  
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
ll dp[50][50][50];
ll dp1[25][50];
int a[25];
ll dfs(int pos,int pre,int sta,int sum,int limit)
{
    if(pos<0)return sum?1:0;
    if(!limit&&dp[pos][sum][sta]!=-1)
        return dp[pos][sum][sta];
    int up=limit?a[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++)
    {
        if(pre==1&&i==3)continue;
        ans+=dfs(pos-1,i,i==1,(sum*10+i)%13,limit&&i==up);
    }
    if(!limit) dp[pos][sum][sta]=ans;
    return ans;
}
ll dfs1(int pos,int pre,int sta,int limit)
{
    if(pos<0)return 1;
    if(!limit&&dp1[pos][sta]!=-1)
        return dp1[pos][sta];
    int up=limit?a[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++)
    {
        if(pre==1&&i==3)continue;
        ans+=dfs1(pos-1,i,i==1,limit&&(i==up));
    }
    if(!limit) dp1[pos][sta]=ans;
    return ans;
}
ll solve(int n)
{
    int t=0;
    ll tt=n;
    ll ans3=n-n/13; //    13 
    while(n)
    {
        a[t++]=n%10;
        n/=10;
    }
    ll ans1=dfs(t-1,-1,0,0,1); //    13  ，    13 
    ll ans2=dfs1(t-1,-1,0,1)-1; //  13 
    return tt-ans2-ans3+ans1;//  
}
int main()
{
    int n;
    memset(dp,-1,sizeof(dp));
    memset(dp1,-1,sizeof(dp1));
    while(~scanf("%d",&n))  printf("%lld
",solve(n)); 


    return 0;
}

Lottie를 사용하여 React 응용 프로그램의 애니메이션을 설정하는 방법
diverta 2019 B-Picking Up 해설

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage