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

shinzAnmono · 2025-02-23 11:24:43 · 题解

设 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) 的。

#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;
}