首页 > 其他 > 详细

uva 11361 - Investigating Div-Sum Property(数位dp)

时间:2016-07-24 11:56:06      阅读:88      评论:0      收藏:0      [点我收藏+]

简单的数位dp题,题意是求区间内的一种数的个数,这种数的本身和各个位置上的数之和能除尽给定的k(k <= 10000)。

dp[20][10000][100]也是可以过的,但是因为各位置上的数之和不会超过100。所以k>=100的情况其实可以直接返回0。

所以dp[20][110][110]足够了(因为懒的想,所以通常数组开大点...)。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define ll long long
int dig[20];
ll k;
ll dp[20][110][110];
ll dfs(int pos, ll num, ll sum, int lim) {
    if(pos == -1) return (num % k == 0) && (sum % k == 0);
    if(!lim && dp[pos][num][sum] != -1) return dp[pos][num][sum];
    int End = lim ? dig[pos] : 9;
    ll ret = 0;
    for(int i = 0; i <= End; i++) {
        ret += dfs(pos - 1, (num * 10 + i) % k, sum + i, lim && (i == End));
    }
    if(!lim) dp[pos][num][sum] = ret;
    return ret;
}

ll func(ll num) {
    int n = 0;
    while(num) {
        dig[n++] = num % 10;
        num /= 10;
    }
    if(k >= 100) return 0;
    return dfs(n - 1, 0, 0, 1);
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        ll l, r;
        scanf("%lld %lld %lld", &l, &r, &k);
        memset(dp, -1, sizeof(dp));
        printf("%lld\n", func(r) - func(l-1));
    }
}

 

uva 11361 - Investigating Div-Sum Property(数位dp)

原文:http://www.cnblogs.com/lonewanderer/p/5700280.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!