X mod f(x) HDU - 4389(디지털 dp)

2025 단어 디지털 dpDP 
Here is a function f(x):
　　　int f ( int x ) {
　　　    if ( x == 0 ) return 0;
　　　    return f ( x / 10 ) + x % 10;
　　　}

　　　Now, you want to know, in a given interval [A, B] (1 <= A <= B <= 10 9), how many integer x that mod f(x) equal to 0.
Input
　　　The first line has an integer T (1 <= T <= 50), indicate the number of test cases.  　　　Each test case has two integers A, B. 
Output
　　　For each test case, output only one line containing the case number and an integer indicated the number of x. 
Sample Input 
2
1 10
11 20

Sample Output 
Case 1: 10
Case 2: 3

제목: x% f (x) 가 0인 x의 개수 f (x) 는 x의 한 자릿수와
최대 범위는 1e9이고 9999999시 f(x)는 최대 81이기 때문에 매 f(x)를 일일이 열거하면 81번의 일반적인 디지털 dp로 한다.
코드 보기:
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll; 
int a[20];
int dp[10][90][90][90];
int dfs(int pos,int sta,int sx,int lead,int limit)
{
    if(pos<0){
        if(lead==sx&&!sta)return 1;
        return 0;
    }
    if(!limit&&dp[pos][sx][lead][sta]!=-1)return dp[pos][sx][lead][sta];
    int up=limit?a[pos]:9;
    int ans=0;
    for(int i=0;i<=up;i++)
    {
        ans += dfs(pos - 1, (sta * 10 + i)%sx,sx,(lead + i), limit && i == up);
    }
    if(!limit) dp[pos][sx][lead][sta]=ans;
    return ans;
}
int solve(int x)
{
    int t=0;
    while(x)
    {
        a[t++]=x%10;
        x/=10;
    }
    int ans=0;
    for(int i=1;i<=81;i++)
        ans+=dfs(t-1,0,i,0,1);
    return ans;
}
int main()
{
    int T,t=1;
    memset(dp,-1,sizeof(dp));
    cin>>T;
    while(T--)
    {
        int l,r;
        cin>>l>>r;
        printf("Case %d: %d
",t++,solve(r)-solve(l-1));
    }
    return 0;
}

hiho12주 트리 dp
Nefry Cloud App 만들기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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