[ CodeVS冲杯之路 ] P1011

　不充钱，你怎么AC？

一开始以为是道数学题，列出了一个公式

后面验证，发现只能推出第一次，后面的还需要迭代，推翻这个公式

又去瞟了一眼数据范围，只有1000，显然直接暴力DFS

每层直接从0到枚，如果该层是0直接ans++

时间复杂度O(nlog₂n)

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<algorithm>
 7 using namespace std;
 8 
 9 int n,ans;
10 void dfs(int x)
11 {
12     if (x==0)
13     {
14         ans++;
15         return;
16     }
17     int i;
18     for (i=0;i<=x/2;i++) dfs(i);
19 }
20 int main()
21 {
22     scanf("%d",&n);
23     ans=0;
24     dfs(n);
25     printf("%d
",ans);
26     return 0;
27 }