首页 > 搜索 > DFS搜索 > HDU 4734-F(x)-动态规划-[解题报告]HOJ
2015
09-17

HDU 4734-F(x)-动态规划-[解题报告]HOJ

F(x)

问题描述 :

For a decimal number x with n digits (AnAn-1An-2 … A2A1), we define its weight as F(x) = An * 2n-1 + An-1 * 2n-2 + … + A2 * 2 + A1 * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).

输入:

The first line has a number T (T <= 10000) , indicating the number of test cases.
For each test case, there are two numbers A and B (0 <= A,B < 109)

输出:

The first line has a number T (T <= 10000) , indicating the number of test cases.
For each test case, there are two numbers A and B (0 <= A,B < 109)

样例输入:

3
0 100
1 10
5 100

样例输出:

Case #1: 1
Case #2: 2
Case #3: 13

比赛的时候先写了个裸的数位dp T掉了,然后加加剪枝过了

#include <cstdio>
#include <cstring>
using namespace std;

int len,lim;
int num[20],mi[20],mii[20];
int dp[10][5000];

int dfs(int pos,int sta,int doing){
    if(pos==-1){
        if(sta<=lim) return 1;
        return 0;
    }
    if(!doing){
        if(dp[pos][sta]!=-1) return dp[pos][sta];
    }
    int sum=0;
    int l=0,r;
    if(doing) r=num[pos];
    else r=9;
    for(int i=l;i<=r;i++){
        int tem=sta+i*mi[pos];
        if(!doing && tem+9*(mi[pos]-1)<=lim) sum+=mii[pos];
        else if(tem>lim) ;
        else if(tem==lim){
            sum++;
        }
        else{
            if(doing && i==r)
                sum+=dfs(pos-1,tem,1);
            else sum+=dfs(pos-1,tem,0);
        }
    }
    if(!doing) dp[pos][sta]=sum;
    return sum;
}

int solve(int b){
    int i=0;
    while(b){
        num[i++]=b%10;
        b/=10;
    }
    len=i;
    memset(dp,-1,sizeof(dp));
    return dfs(len-1,0,1);
}

int main(){
    //freopen("a.txt","r",stdin);
    //freopen("c.txt","w",stdout);
    int t,T;
    int tem,a,b;
    mi[0]=1;mii[0]=1;
    for(int i=1;i<10;i++) mi[i]=mi[i-1]*2,mii[i]=mii[i-1]*10;
    scanf("%d",&T);
    for(t=1;t<=T;t++){
        scanf("%d %d",&a,&b);
        lim=0;tem=1;
        while(a){
            lim+=tem*(a%10);
            tem*=2;
            a/=10;
        }
        printf("Case #%d: %d\n",t,solve(b));
    }
    return 0;
}

刚刚看了别人的思路,发现自己状态设计的有点问题,我用dp[i][j]表示 i位之前的高位的和为j,低i位一共多少种取法满足总和<lim

其实可以这么表示状态的,dp[i][j]表示不管高位低i位的和<=j一共有多少取法,这样既可以写成记忆化的形式,也可以预处理出来。

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/waitfor_/article/details/11696099