ITKeyword,专注技术干货聚合推荐

注册 | 登录

HDU 5787 K-wolf Number

chy20142109 分享于 2016-08-03

推荐:HDU 5787 K-wolf Number(数位DP)

题目链接:点击打开链接 思路: 我们用dp[cur][a][b][c][d][p]表示当前到了第cur位,前四位分别是abcd并且当前是否已经小于给定的数的方案数。  我们分别算出L和

2019阿里云全部产品优惠券(新购或升级都可以使用,强烈推荐)
领取地址https://promotion.aliyun.com/ntms/yunparter/invite.html

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5787 题意:求区间[L,R]内,任意相邻k位(如果位数不足k,就是全部的数位)没有两两相同的数位的数的个数。 思路:数位DP,因为K<=5,我们最多需要保存下来当前位的前4位就足够了。因为dp[pos][p1][p2][p3][p4]表示,现在枚举取第pos位,pos位之前的四位分别为p1,p2,p3,p4,p4是pos的上一位。那么p1~p4的范围就是0~9,但是数是没有前导0的,而且k可能为2,3,4,不需要保存到前4位,所以我们令p = 10来表示这一位不需要保存,也许可能是前导0,也许是不需要保存。那么dfs函数可以写成 dfs( int pos , int p1 , int p2 , int p3 , int p4 , bool flag ) flag表示pos位能否取到全部的数位(0~9)还是会受到前面最高位的影响只能取一部分。那么统计下一位的时候就可以分为两种情况:1、pos位之前都取的0,而pos位也取0,一直都是前导零。2、pos位取的i去和p判断一下有没有重复(根据k来判断需要比较几个p),假设这种情况,K = 3,而我们现在正在取第二位,i会和p4和p3去比较一下,但是只有p4是我们取过的值,不过p3此时是10,所以也是可以向下统计的。 #include <cstdio>#include <cmath>#include <cstring>#include <string>#include <cstdlib>#include <iostream>#include <algorithm>#include <stack>#include <map>#include <set>#include <vector>#include <sstream>#include <queue>#include <utility>using namespace std;#define rep(i,j,k) for (int i=j;i<=k;i++)#define Rrep(i,j,k) for (int i=j;i>=k;i--)#define Clean(x,y) memset(x,y,sizeof(x))#define LL long long#define ULL unsigned long long#define inf 0x7fffffffLL L,R;int K;LL dp[19][11][11][11][11];int digit[20];bool check( int a , int b,int c,int d,int now ) //根据K来判断需要和哪些p做比较{

if ( K == 2 )

return now

推荐:hdu3652---B-number(数位dp)

Problem Description A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string “13” and can be divid

!= d;

else if ( K == 3 )

return now != d && now != c;

else if ( K == 4 )

return now != d && now != c && now != b;

return now != d && now != c && now != b && now != a;}LL dfs( int pos , int p1 , int p2 , int p3 , int p4 , bool flag ){

if ( pos == 0 ) //全部取完,若p4还是10,说明全部取了0,即全部为前导零。

return p4 != 10;

if ( !flag && dp[pos][p1][p2][p3][p4] != -1 ) return dp[pos][p1][p2][p3][p4];//记忆化直接返回答案

int ed = flag?digit[pos]:9;//最大可以取的数

LL ans = 0;

rep(i,0,ed)

{

if ( i == 0 && p4 == 10 ) //pos位及其之前全部为0

ans += dfs( pos - 1 , 10 , 10 , 10 , 10 , flag && i == ed );

else

if ( check(p1,p2,p3,p4,i) )

ans += dfs( pos - 1 , p2 , p3 , p4 , i , flag && i == ed );

}

if ( !flag )

dp[pos][p1][p2][p3][p4] = ans;

return ans;}LL cal( LL x ){

if ( x <= 0 ) return 0;

LL temp = x;

int len = 0;

while( temp )

{

digit[++len] = temp % 10;

temp /= 10;

}

return dfs( len , 10 , 10 , 10 , 10 , 1 );}int main(){

init();

while( scanf("%I64d %I64d %d",&L,&R,&K) == 3 )

{

Clean(dp,-1);

printf("%I64d\n",cal(R)-cal(L-1));

}

return 0;}

推荐:HDU --3652--b_number--数位DP

求出区间内有13作为连续子串且是13的倍数的数字的个数 思路:dp数组增加一维用来表示状态数字对13取模的余数就好了,然后状态转移的时候按照找出含有13的数字的

题目链接:http://acm.hdu.edu.cn/showproblem.phppid=5787 题意:求区间[L,R]内,任意相邻k位(如果位数不足k,就是全部的数位)没有两两相同的数位的数的个数。 思路:数位DP,因为K<=5,我们

相关阅读排行


用户评论

游客

相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。