程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LightOJ 1068 Investigation (數位dp)

LightOJ 1068 Investigation (數位dp)

編輯：C++入門知識

LightOJ 1068 Investigation (數位dp)

求出區間[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 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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
,item);
			continue;
		}
		memset(dp,-1,sizeof(dp));
		printf(Case %d: %d
,item,cal(b) - cal(a-1));
	}
	return 0;
}