LightOJ 1068 Investigation (数位dp)

本文主要是介绍LightOJ 1068 Investigation (数位dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://www.lightoj.com/volume_showproblem.php?problem=1068

求出区间[A,B]内能被K整除且各位数字之和也能被K整除的数的个数。（1 ≤ A ≤ B < 2³¹ and 0 < K < 10000）

算是最简单的数位dp了，k在这里是10000，三维数组都开不开。但是想想会发现A,B最多有10位，各位数字之和不会超过90，那么当 k >= 90时，就不用dp，因为个位数字之和对k取余不会等于0。所以数组只需开到dp[12][90][90]。

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 4010;int dp[15][92][92];
int a,b,k;
int dig[15];int dfs(int len, int mod1, int mod2, int up)
{if(len == 0)return mod1 == 0 && mod2 == 0;if(!up && dp[len][mod1][mod2] != -1)return dp[len][mod1][mod2];int res = 0;int n = up ? dig[len] : 9;for(int i = 0; i <= n; i++){int tmod1 = (mod1*10 + i)%k;int tmod2 = (mod2 + i)%k;res += dfs(len-1,tmod1,tmod2,up&&i==n);}if(!up)dp[len][mod1][mod2] = res;return res;
}int cal(int num)
{int len = 0;while(num){dig[++len] = num%10;num /= 10;}return dfs(len,0,0,1);
}int main()
{int test;scanf("%d",&test);for(int item = 1; item <= test; item++){scanf("%d %d %d",&a,&b,&k);if(k >= 90){printf("Case %d: 0\n",item);continue;}memset(dp,-1,sizeof(dp));printf("Case %d: %d\n",item,cal(b) - cal(a-1));}return 0;
}

这篇关于LightOJ 1068 Investigation (数位dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---