HDU_4734_F(x)_数位dp

HDU_4734_F(x)_数位dp

F(x)

Time Limit: 1000/500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 15070    Accepted Submission(s): 5761

 

// 如果对于每一个f(a)都求一遍答案 空间复杂度受不了 O( 9*4600*4600 )

// dp[f(a)][now][sum]: 在约束==f(a)时 当前数位进行到now位 now+1~pos位的加权和为sum

// 于是考虑做减法

// dp[now][re]: 当前进行到了now位 剩余量为re

// 对于不同的f(a) 只要最后的剩余量re>=0 就说明f(a)>=sum 当前dp遍历的所有数字都是答案

// 确定上限 
#include
using namespace std;
 
int main()
{
    int sum=0;
    for( int i=0;i<9;i++ )
    {
        sum+=9*( 1<
    }
    cout<// 4599
    cout<<( 1<<14 )<
    
    return 0;
}
// A,B < 1e9 --> 9个9 --> 4599
 
// 如果对于每一个f(a)都求一遍答案 空间复杂度受不了 O( 9*4600*4600 )
// dp[f(a)][now][sum]: 在约束==f(a)时 当前数位进行到now位 now+1~pos位的加权和为sum
// 于是考虑做减法 
// dp[now][re]: 当前进行到了now位 剩余量为re 
// 对于不同的f(a) 只要最后的剩余量re>=0 就说明f(a)>=sum 当前dp遍历的所有数字都是答案
 
// HDU_4734_F(x)_数位dp
#include
using namespace std;
#define int long long
 
const int N=11;
int dp[N][11111];
int in[N];
int x,y;
int stdd;
 
int dfs( int now,int re,bool limit )
{
    if( re<0 ) return 0;
    if( now<=0 ) return ( re>=0 ) ;
    if( limit==0 && ~dp[now][re] ) return dp[now][re];
 
    int up=limit ? in[now] : 9 ;
    int ans=0;
 
    for( int i=0;i<=up;i++ )
        ans+=dfs( now-1,re-i*( 1<<(now-1) ),limit && i==in[now] );
    								// 
    if( limit==0 ) dp[now][re]=ans;
    return ans;
}
 
int f( int n )
{
    int pos=0;
    while( n ) in[++pos]=n%10,n/=10;
 
    return dfs( pos,stdd,1 );
}
 
void f_stdd( int n )
{
    stdd=0;
    int r=1;
    while( n ) stdd+=n%10*r,n/=10,r<<=1;
}
 
signed main()
{
    memset( dp,-1,sizeof( dp ) );
 
    int t,i,x,y;
 
    scanf("%lld",&t);
    for( i=1;i<=t;i++ )
    {   
        scanf("%lld%lld",&x,&y);
        f_stdd( x );
        printf("Case #%lld: %lld\n",i,f(y) ); 
    }
    return 0;
}