HDU 3652 B-number【デジタルDP】

4973 ワード

B-number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5153 Accepted Submission(s): 2962
Problem Description
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

Author

wqb0039

Source

2010 Asia Regional Chengdu Site —— Online Contest

Recommend

lcy | We have carefully selected several similar problems for you: 3651 3655 3654 3653 3659

#pragma comment(linker, "/STACK:102400000,102400000") 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define Pi acos(-1.0)
using namespace std;

typedef long long  ll;
ll DP[20][10][15];
int DIG[20];
ll  dfs(int pos,int status,int limit,int mod)
{
    if(pos < 0)
        return  status==2 && !mod;
    if(!limit && DP[pos][status][mod] != -1)
        return    DP[pos][status][mod];
    int   end = limit ? DIG[pos] : 9;
    ll    ret = 0;
    
   	for(int i = 0;i <= end;i ++){
   		int nmod = (mod * 10 + i) % 13;
   		if(status==2 ||(status==1 && i==3)){
		   	ret += dfs(pos - 1,2,limit && (i == end),nmod);
	   	}
		else if(i==1){
			ret += dfs(pos - 1,1,limit && (i == end),nmod);
		}
		else{
			ret += dfs(pos - 1,0,limit && (i == end),nmod);
		}
    }
    

        

    //DP      、       
    if(!limit)
        DP[pos][status][mod]= ret;

    return    ret;
}
ll slove(ll x){
	ll tem = x;
	memset(DP,-1,sizeof DP);
	int num = 0;
	while(x){
		DIG[num] = x%10;
		x/=10;
		num++;
	}
	ll ans = 0;
	ans = dfs(num-1,0,1,0);
	
}
int main(){
	ll n, m;
	int t;
	while(~scanf("%lld", &n)){
		printf("%lld
", slove(n));
	}


}

HDU 1394(最小逆シーケンス数)【セグメントツリーでも使用可能】

コンパイルエラーCaused by:com.android.tools.r 8.CompilationFailedException:Compilation failed to complete