I - 22数

$dfs$ 暴力
时间复杂度： $2000w$ 左右

#include
using namespace std;

typedef long long LL;
LL n,ans;

void dfs(LL x,LL len,LL sum)
{
	if(x>n||sum>20) return ;
	if(x && len*2==sum) ans++;
	for(int i=0;i<=9;i++)
	{
		LL y=x*10+i;
		if(y && y<=n) 
            dfs(y,len+1,sum+i);
	}
}

int main()
{
	cin>>n;
	dfs(0,0,0);
	cout<<ans;
	return 0;
}
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