数位dp H - F(x) HDU

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

一般数位dp表示的是数的性质，这个题目也是一样，但是我们求出来的是一个函数的值，怎么把这个值转化成一类数，然后再用dp数字来表示这个数的性质呢?

这个我觉得挺麻烦的，很自然发现了这个f[x]并不是很大，最大应该就是10000左右，所以就可以放入数组里面表示

所以就有dp[pos][sum] 但是呢，这个是有问题的，因为如果你用sum来表示前缀和，那就无法进行记忆化，这个dp数组就会出现问题。

然后我就懵了，然后没忍住又去看了一下题解，题解说后面的那维不存前缀和sum，而是存ex-sum 表示前面以及有了sum后面还需要ex-sum这个的数的个数

然后这个就是对的了，至于为什么，你可以理解为我要求一类数，这类数有pos位，然后后面这类数的f(x)必须小于等于sum，这就是一种数的性质。

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <queue>

#include <vector>

#include <iostream>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

typedef long long ll;

int a[];

int f(int x)

{

    int pos = ;

    int ans = ;

    while(x)

    {

        ans += (x % )*( << pos);

        x /= ;

        pos++;

    }

    return ans;

}

int ex;

int dp[][];

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

{

    if (pos == -) return sum <= ex;

    if (sum > ex) return ;

    if (!limit&&dp[pos][ex-sum] != -) return dp[pos][ex-sum];

    int up = limit ? a[pos] : ;

    int ans = ;

    for(int i=;i<=up;i++)

    {

        ans += dfs(pos - , sum + i * (<<pos), limit && (i == up));

    }

    if (!limit) dp[pos][ex-sum] = ans;

    return ans;

}

ll solve(ll x)

{

    int pos = ;

    while(x)

    {

        a[pos++] = x % ;

        x /= ;

    }

    return dfs(pos - , , );

}

int main()

{

    int t;

    scanf("%d", &t);

    memset(dp, -, sizeof(dp));

    for(int cas=;cas<=t;cas++)

    {

        int x, y;

        scanf("%d%d", &x, &y);

        ex = f(x);

        int ans = solve(y);

        printf("Case #%d: %d\n",cas, ans);

    }

    return ;

}

数位dp

巴特西

数位dp H - F(x) HDU - 4734

最新文章

热门文章