hdu4734 F(x) 數位dp

http://acm.hdu.edu.cn/showproblem.php?pid=4734

題意：A[i]為數x的十進制第i位,是以有x：A[n]A[n-1]...A[1]

F(x)=A[n]*2^(n-1)+A[n-1]*2^(n-2)+...+A[1]*1。

現在求x∈[0,B]，F[x]<=F[A]。這樣的x有多少個。

題解：設計數位dp的dfs函數。

int dfs(int pos,int pre,bool limit)

這裡的pre換成F[A]-(1<<(pos-1))。如果pre<0，搜尋結束，反之繼續搜尋。

代碼：

#include<bits/stdc++.h>
#define debug cout<<"aaa"<<endl
#define d(a) cout<<a<<endl
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define MIN_INT (-2147483647-1)
#define MAX_INT 2147483647
#define MAX_LL 9223372036854775807i64
#define MIN_LL (-9223372036854775807i64-1)
using namespace std;

const int N = 1000000 + 5;
const int mod = 1000000000 + 7;
const double eps = 1e-8;
int dp[10][1<<15];
int DIG[10];

int dfs(int pos,int pre,bool limit){
	if(pos<1){
		return 1;
	} 
	if(!limit&&dp[pos][pre]!=-1){
		return dp[pos][pre];
	}
	int end=limit?DIG[pos]:9;
	int ret=0;
    for(int i=0;i<=end;i++){
    	int temp=pre-i*(1<<(pos-1));
    	if(temp<0) continue;
    	ret+=dfs(pos-1,temp,limit&&(i==end));
    }
    if(!limit){
    	dp[pos][pre]=ret;
    }
    return ret;
}

int F(int x){
	int res=0,cnt=0;
	while(x){
		res+=(x%10)*(1<<cnt);
		x/=10,cnt++;
	}
	return res;
}

int solve(int x,int y){
	mem(DIG,0);
	y=F(y);
	int p=1;
	while(x){
		DIG[p++]=x%10;
		x/=10;
	}
	p--;
	return dfs(p,y,1);
}

int main(){
	int t,cas=0;
	int n,m;
	mem(dp,-1);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		printf("Case #%d: %d\n",++cas,solve(m,n));
	}
	return 0;
}