题目链接
Balanced Number
题目描述
定义一种数叫做Balanced number，这样子的数满足，选取一个位置后，分成左右两边然后向左向右分别乘上1，2，3，4后相加相等。
思路
能够枚举的位置最多18位，所以可以考虑暴力枚举位置，并且，每一个数至多有一个位置能够满足该定义。
所以我们可以设dp[len][pos][sum],代表第len个位置，pos是我们枚举的中点位置，sum表示该数当前的和，如果len==-1，判断sum是否==0就好。
其中可以剪枝，也就是当sum<0的时候就可以返回0了，因为sum<0后sum后面一定会更小不会更大了。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[20][20][2000];
int a[20];
ll dfs(int len,int pos,int sum,bool limit)
{
if(len==-1)return sum?0:1;
if(sum<0)return 0;
if(!limit&&dp[len][pos][sum]!=-1)return dp[len][pos][sum];
int up = limit?a[len]:9;
ll temp = 0;
for(int i=0;i<=up;i++)
{
temp += dfs(len-1,pos,sum+(len-pos)*i,i==up&&limit);
}
return limit?temp:dp[len][pos][sum]=temp;
}
ll solve(ll x)
{
ll ans = 0;
int p = 0;
while(x)
{
a[p++]=x%10;
x/=10;
}
for(int i=0;i<p;i++)
ans+=dfs(p-1,i,0,1);
return ans-p+1;
}
int main(){
int t;
memset(dp,-1,sizeof(dp));
scanf("%d",&t);
while(t--)
{
ll l,r;
cin>>l>>r;
printf("%lld\n",solve(r)-solve(l-1));
}
return 0;
}
|