F(x) HDU - 4734

点击打开链接

这道题应该把dp[i][j]定义为a的权值减去高i位的加权值后是j的情况下有多少可行解 这样每一次a和fa值都不同 但不影响dp[i][j]的正确性

如果只是简单的把dp[i][j]定义为高i位的加权值是j的情况下有多少可行解 那么每换一个样例都要初始化一次 必然T。。因为只知道高位权值的情况下 不知道与a的权值还相差多少 而a在每个样例中都是不一样的

#include <bits/stdc++.h>
using namespace std;

int dp[20][10000];
int num[20];

int dfs(int pos,int val,int lim)
{
    int i,up,res;
    if(val<0) return 0;
    if(pos==-1) return 1;
    if(!lim&&dp[pos][val]!=-1) return dp[pos][val];
    if(lim==1) up=num[pos];
    else up=9;
    res=0;
    for(i=0;i<=up;i++)
    {
        res+=dfs(pos-1,val-(1<<pos)*i,lim&&i==up);
    }
    if(!lim) dp[pos][val]=res;
    return res;
}

int solve(int a,int b)
{
    int tem[20];
    int i,cnt1,cnt2,fa;
    cnt1=0;
    while(b>0)
    {
        num[cnt1++]=b%10;
        b/=10;
    }
    cnt2=0;
    while(a>0)
    {
        tem[cnt2++]=a%10;
        a/=10;
    }
    fa=0;
    for(i=cnt2-1;i>=0;i--)
    {
        fa*=2;
        fa+=tem[i];
    }
    return dfs(cnt1-1,fa,1);
}

int main()
{
    int t,cas,a,b;
    memset(dp,-1,sizeof(dp));
    scanf("%d",&t);
    for(cas=1;cas<=t;cas++)
    {
        scanf("%d%d",&a,&b);
        printf("Case #%d: %d\n",cas,solve(a,b));
    }
    return 0;
}