本文主要是介绍HDU 2089 不要62 HDU 3652 B-number(初级数位DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU 2089 不要62
解题思路
dp[len][mark]中 len 代表当前处理的数位，mark 标记上一位的数字是否为6。
代码实现
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 10
int dp[maxn][2],num[maxn];
int dfs(int len,bool mark,bool limit) //当前所处理数位、标记上一位是否为6、标记该位置是否有上限限制
{if(len==0)return 1;if(!limit&&dp[len][mark]!=-1) return dp[len][mark]; //若没有上限限制且dp[len][mark]已经标记过直接返回数值。//如假设num[]为9876且当前数位为第4位，在开始枚举第四位可行数字***0时，//3、2、1位的所满足的情况和已经记录下来了，下一个枚举可行数字***1时直接返回就好int maxx=limit?num[len]:9; //存在上限限制：如对于9876，第4位最大只能为6int cnt=0; //标记在当前数位长度下满足条件的和for(int i=0; i<=maxx; i++) //对当前数位枚举可行数字{if((mark&&i==2)||i==4) //如果为62或4直接跳过continue;cnt+=dfs(len-1,i==6,limit&&(i==maxx)); //枚举下一个数位、当前数位（下一个数位的上一个数位）是否为6、//下一个数位是否存在上限限制，//如num[]数组为9876，如果当前数位是第4位即limit=1,当i==6时，第3位则最大只能为7,则limit参数传入为1}if(!limit) //如果有限制，那么当前数字枚举的范围便不是0~9,不满足记忆的条件，在其他情况下是不能使用的。dp[len][mark]=cnt;return cnt;
}int solve(int n)
{int t=0;memset(num,0,sizeof(num));while(n>0){num[++t]=n%10;n/=10;}return dfs(t,0,1);
}int main()
{int a,b;while(~scanf("%d %d",&a,&b)){memset(dp,-1,sizeof(dp));if(a==0&&b==0) break;printf("%d\n",solve(b)-solve(a-1));}return 0;
}
HDU 3652 B-number
解题思路
dp[len][mod][mark][hav]中 len 代表当前处理的数位，mod代表上一步的值%13是否为0，mark标记上一位是否为1，hav标记当前情况下是否已经含有13。
其余思路与上一题大致一致。
代码实现
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[15][13][2][2],num[15];
int dfs(int len,int mod,bool mark,bool hav,bool limit)
{if(len==0)return mod==0&&hav; //当前数字%13为0且含有子串13才能贡献1if(!limit&&dp[len][mod][mark][hav]!=-1) return dp[len][mod][mark][hav];int maxx=limit?num[len]:9;int cnt=0;for(int i=0;i<=maxx;i++){cnt+=dfs(len-1,(mod*10+i)%13,i==1,hav||(mark&&i==3),limit&&(i==maxx));}if(!limit) dp[len][mod][mark][hav]=cnt;return cnt;
}
int solve(int n)
{int t=0;memset(num,0,sizeof(num));while(n){num[++t]=n%10;n/=10;}return dfs(t,0,0,0,1);
}
int main()
{int a;while(~scanf("%d",&a)){memset(dp,-1,sizeof(dp));printf("%d\n",solve(a));}return 0;
}
这篇关于HDU 2089 不要62 HDU 3652 B-number(初级数位DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
