8 TLE
查看原帖
8 TLE
420102
phmaprostrate楼主2021/8/14 21:12

为啥会TLE?

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int num[20];
int dp[20][200][200];
int mod;
int dfs(int len,int sum,int p,bool limit){
    if(sum + 9 * len < mod) return 0;
	if(len == 0) return p==0 &&sum == mod;
	if(!limit && dp[len][sum][p] != -1) return dp[len][sum][p];
	int ans = 0;
 int up = 9;
	if(limit) up = num[len];
//	cout<<1<<" ";
	for( int i = 0;i <= up;i++){
		ans += dfs(len - 1,sum + i,(10 * p + i) % mod,i == up &&limit);
	}
	if(limit) dp[len][sum][p] = ans;
	return ans;
}
int solve(int x){
	int len = 0;
	int ans = 0 ;
	while(x){
		num[++len] = x % 10;
		x /= 10;
	}
	for(mod = 1;mod <= len * 9;mod++){
	        memset(dp,-1,sizeof(dp));
	    ans += dfs(len,0,0,1);
	}
 return ans;
}
signed main(){
	cin >>a>>b;
	cout<<solve(b) - solve(a - 1);
	return 0;
} 
2021/8/14 21:12
加载中...