你试试记忆化搜索
by αnonymous @ 2019-03-02 10:41:45
@[banana1105](/space/show?uid=166726) 你再咋也要加个记忆化啊。。。
by ieeqwq @ 2019-03-02 10:45:39
$T(n)=\sum\limits_{i=1}^{n/2}T(i)$
这个咋算啊
by NaCly_Fish @ 2019-03-02 10:46:51
@[Sky_Liu](/space/show?uid=93538) @[wzsCD](/space/show?uid=127284) 谢谢Thanks♪(･ω･)ﾉ！
by banana1105 @ 2019-03-02 10:52:10
O(玄学)
by wwlw @ 2019-03-02 10:52:30
编了一个记忆化的输入1000只要跑806毫秒！谢谢Thanks♪(･ω･)ﾉ！
```
#include<iostream>
using namespace std;
int rrt[1000]={0};
int out(int num){
if(rrt[num])return rrt[num];
int rt=1;
for(int i=1;i<=num/2;++i)rt+=out(i);
rrt[num]=rt;
return rt;
}
int main(){
int n;
cin>>n;
cout<<out(n);
return 0;
}
```
还AC了！
by banana1105 @ 2019-03-02 10:58:15
新版O(N)
by banana1105 @ 2019-03-02 11:02:35
@[NaCly_Fish](/space/show?uid=115864)
$T(n)=T(n-1)+T(\frac{n}{2})$
by Adove @ 2019-03-02 11:04:49
@[A·H_](/space/show?uid=31293) 刚想发出来，被抢先了QAQ
by NaCly_Fish @ 2019-03-02 11:11:39
这个东西似乎是指数级增长的
也就是$\Theta(a^n)$，这个$a$应该不大
by NaCly_Fish @ 2019-03-02 11:12:32