HDU3709 Balanced Number

2010成都, DP, 数位DP

　　2010 ACM/ICPC 成都赛区现场赛

　　题意：若选定一个数的第i位作为支点，将数分为左右两部分，令第j个位置的价值为d[j]*abs(j-i)，若左右两边的价值和相等，则该数为平衡数。对于每个询问，输出该区间内平衡数的个数。- 原题链接

　　常规的数位DP题，最开始wa在直接return f[pos][st]这个地方，因为limit的取值对同一组pos和st是有影响的，可以直接在f中加上limit这一维，也可以根据limit取值特殊判断。


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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=20+5, S=1500+10;
typedef long long lint;
int T, n, upnum[N];
lint x, y, f[N][S];
void Init(lint num)
{
	n=0;
	while(num)
	{
		upnum[++n]=num%10;
		num/=10ll;
	}
	return ;
}
lint DP(int pos, int st, int pt, bool limit)
{
	if(pos==0)	return f[pos][st]=(st==0);
	if(!limit && f[pos][st]!=-1)	return f[pos][st];
	lint ans=0;
	int up= limit ? upnum[pos] : 9;
	for(int i=0; i<=up; i++)
	{
		if(pos>=pt)	ans+=DP(pos-1, st+i*(pos-pt), pt, (limit && i==upnum[pos]));
		else if(st-i*(pt-pos)>=0)	ans+=DP(pos-1, st-i*(pt-pos), pt, (limit && i==upnum[pos]));
	}
	if(!limit)	f[pos][st]=ans;
	return ans;
}
lint Work(lint num)
{
	if(num<10)	return num+1;
	Init(num);
	lint ans=0;
	for(int i=1; i<=n; i++)
	{
		memset(f, -1, sizeof f);
		ans+=DP(n, 0, i, true);
	}
	return ans-n+1;
}
int main()
{
	scanf("%d", &T);
	int tt=0;
	while(T--)
	{
		scanf("%lld%lld", &x, &y);
		printf("%lld\n", Work(y)-Work(x-1));
	}
	return 0;
}