HDU 3709 数位dp

17-01-16 来源：[db:作者]

收藏我要投稿

HDU 3709 数位dp：定义一种平衡数，就是按照十进制数位上选取一位当作支点，左右两边的数位计算力矩后相等，即为平衡数。

所谓力矩，就是拿数位上的数字乘上到支点的距离。举例来说，4139，如果选3作为支点，左边的力矩为4*2+1*1=9，右边的力矩为9*1=9，左边等于右边，所以4139是一个平衡数。题目要求计算出区间[x,y]之间的平衡数的个数。

思路：

显然数位dp。关键是在于状态的设计，这里还是欠缺不少。对于平衡的题目设计状态，经常要用到平衡度的思想，所谓平衡度就是定义为右边的重量-左边的重量，当平衡度为0时显然为平衡。

这里要注意到，任意一个数，如果是平衡数，只存在一个数位当支点满足条件，不存在第二组解。所以如果我们设计状态dp[pos][pivot][balance]，其中pos为数位长度，pivot为支点位置，balance为平衡度。这样起码可以保证不同pos不同pivot之间的数一定没有重复。

利用平衡度来设计状态，就很好设计状态转移了，因为平衡状态是由不平衡状态转移过来的。这样只要枚举pivot的位置，将所有的结果相加就可以。

还有一点要注意，枚举一共有pos次，这其中0被多算了pos-1次，因为无论枚举哪个数位做pivot，0都是满足条件的，所以最后结果要减掉。具体细节见代码。

代码：

#include 
using namespace std;
typedef long long ll;

int a[20];
ll dp[20][20][2000];

ll dfs(int pos, int pivot, int balance, bool limit) {
    if (pos == -1) return balance == 0 ? 1 : 0;
    if (!limit && dp[pos][pivot][balance] != -1) return dp[pos][pivot][balance];
    int up = limit ? a[pos] : 9;
    ll res = 0;
    for (int i = 0; i <= up; i++) {
        res += dfs(pos - 1, pivot, balance + (pos - pivot) * i, limit && a[pos] == i);
    }
    if (!limit) dp[pos][pivot][balance] = res;
    return res;
}

ll solve(ll x) {
    int pos = 0;
    while (x) {
        a[pos++] = x % 10;
        x /= 10;
    }
    ll res = 0;
    for (int i = 0; i < pos; i++) {
        res += dfs(pos - 1, i, 0, true);
    }
    return res - pos + 1;
}

int main() {
    int T;
    scanf("%d", &T);
    memset(dp, -1, sizeof(dp));
    while (T--) {
        ll x, y;
        scanf("%I64d%I64d", &x, &y);
        printf("%I64d\n", solve(y) - solve(x - 1));
    }
    return 0;
}

点击复制链接与好友分享!回本站首页