题解：P1028 [NOIP 2001 普及组] 数的计算

设

f_i

表示当

n=i

时的答案，则

f_i=f_1+f_2+\ldots+f_{\left\lfloor n/2\right\rfloor}+1

（因为

n=i

时，序列的第一个数为

i

），初始时

f_1=1

。

直接循环递推求解是

O(n^2)

的，虽然可以通过本题，我们考虑优化。

设

g_i=f_1+f_2+\cdots+f_i

，则转移为

f_i=g_{\left\lfloor n/2\right\rfloor}+1

即可，这样做时间复杂度是

O(n)

的。

CPP

#include<iostream>
#include<algorithm>
const int sz=1010;
int f[sz],g[sz];
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin>>n;
    f[1]=g[1]=1;
    for(int i=2;i<=n;i++)f[i]=g[i/2]+1,g[i]=g[i-1]+f[i];
    std::cout<<f[n]<<"\n";
    return 0;
}

题解：P1028 [NOIP 2001 普及组] 数的计算

文章操作

相关推荐

评论

题解：P1028 [NOIP 2001 普及组] 数的计算