数位DP再来一题。题目链接:HDOJ4389

题意:求【A,B】中有多少个该数能够整除其数位之和的数


分享一发我雨巨的题解,写得比我好多了:雨巨题解

相同的思路,不同的dp构造


F(X)意思为X的各数位之和,X最大是1e9,所以F(X)的范围是1到81。

所以在DP设计的时候,X数位之和要设计成一维


然后又必须有X mod F(X)=0,所以当前的余数需要设计一维,当前的数字和需要设计一维

再加上模板中必有的pos作为一维,所以呢,dp状态定义已经设计好了


dp【pos】【mod】【X】【sum】:从高位到第pos位,除以X的余数是mod,各个位数之和为sum的数的个数

高维DP注意确定好每一维的大小,不然容易MLE

pos最多10位,给个10就足够

mod最大为80,给85足够

X和sum最大为81,给85足够

我定义的是dp[10][85][85][85],不仔细计算随便给100,200之类的值容易MLE,不值得


边界值是pos为0的时候,如果sum==X(说明数位之和相加等于原数,满足了F(X)的定义),而且mod%x==0即该数能够整除数位之和,那么赋值为1,否则为0

状态转移就是对digit【pos-1】的枚举


对于区间【1,n】时,首先按照模板分解n

然后,因为无法确定各个位数之和,所以对于X=1到X=81全部枚举即可,就能求出【1,n】中符合题意的解


#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxn 1050
#define maxnum 1000050
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)

int m,n;
int digit[20];
int dp[10][85][85][85];

int dfs(int pos,int mod,int x,int sum,bool flag){
	if (pos==0) return (x==sum&&mod%sum==0);
	if (flag&&dp[pos][mod][x][sum]!=-1) return dp[pos][mod][x][sum];
	int num=flag?9:digit[pos];
	int ans=0;
	for(int i=0;i<=num;i++){
		int nowmod=(mod*10+i)%x;
		ans+=dfs(pos-1,nowmod,x,sum+i,flag||i<num);
	}
	if (flag) dp[pos][mod][x][sum]=ans;
	return ans;
}

int calc(int n){
	int pos=0;
	int ans=0;
	while(n){
		digit[++pos]=n%10;
		n/=10;
	}
	for(int i=1;i<=81;i++)
		ans+=dfs(pos,0,i,0,0);
	return ans;
}

int main(){
	input;
	int t;
	memset(dp,-1,sizeof(dp));
	scanf("%d",&t);
	for(int Case=1;Case<=t;Case++){
		scanf("%d%d",&m,&n);
		printf("Case %d: %d\n",Case,calc(n)-calc(m-1));
	}
	return 0;
}

提交之前可以测试一下,【1,1e9】答案为多少

来判断需要用int就够,还是__int64