题解 P1028 【数的计算】

· · 题解

Code O(n)

Force 25% O(n^n)

递归是过不了的。。与Fibonacci相似。可以分析递归复杂度。

(n) = \sum_{i=1}^{n/2}f(i)+o(1)

求上界的话，放缩一下：

f(n) = nf(n-1)+o(1)

显然，递推一下就有（n!=O(n^n)），比指数还吓人。。

f(n) = O(n^n) 
#include <bits/stdc++.h>
using namespace std;

int f(int n){
    if(n == 1) return 1;
    int result = 0;
    for(int i = 1; i <= n/2; ++i)  //通项
        result += f(i);
    return result + 1;  //算上自己
}

int main(){
    int n; cin>>n;
    cout<<f(n);
}

Force+记忆剪枝 O(n^2)+O(n)

#include <bits/stdc++.h>
using namespace std;

int f_remember[1005];

int f(int n){
    if(n == 1) return 1;
    if(f_remember[n]) return f_remember[n];
    int result = 0;
    for(int i = 1; i <= n/2; ++i)
        result += f(i);
    return f_remember[n] = result + 1;  //记忆
}

int main(){
    int n; cin>>n;
    cout<<f(n);
}

迭代/传播 O(n^2)+O(n)

此方法相当于记忆剪枝的迭代版改写。

状态方程：（先求小，再求大）

f(n) = \sum_{i=1}^{n/2}f(i), f(1)=1

注意到从递推式的基本项可以向上传播。

#include <bits/stdc++.h>
using namespace std;

int f[1005];

int main(){
    int n; cin>>n;
    f[1] = 1;
    for(int i = 2; i <= n; ++i){
        for(int j = 1; j <= i/2; ++j)  //通项
            f[i] += f[j];
        f[i] ++;  //算上自己
    }
    cout<<f[n];
}

递推优化 O(n)+O(0.5n)

注意到，

f(n) = \sum_{i=1}^{n/2}f(i)+o(1),\quad f(n-1) = \sum_{i=1}^{(n-1)/2}f(i)+o(1)

显然每一步的求和中，存在大量的重复计算。

递推公式可以优化为：

f(n) = SUM(n/2)+1,\quad SUM(i) = SUM(i-1)+f(i)

这时内部求和的O(n)变为分摊常数。同样可以采用递归或迭代方法。

记忆剪枝 O(n)+O(n)

#include <bits/stdc++.h>
using namespace std;

int f[1005], sum[505];

int F(int i); int Sum(int i);

int main(){
    int n; cin>>n;
    f[1] = sum[1] = 1;
    cout<<F(n);
}

int F(int i){
    if(f[i]) return f[i]; //剪枝
    return f[i] = Sum(i/2) + 1;  //利用赋值，记忆
}

int Sum(int i){
    if(sum[i]) return sum[i]; //剪枝
    return sum[i] = Sum(i - 1) + F(i);  //利用赋值，记忆
}

迭代传播 O(n)+O(n)

#include <bits/stdc++.h>
using namespace std;

int f[1005], sum[505];

int main(){
    int n; cin>>n;
    f[1] = 1;
    for(int i = 2; i <= n; ++i){
        sum[i/2] = sum[i/2 - 1] + f[i/2];
        f[i] = sum[i/2] + 1;
    }
    cout<<f[n];
}

就地传播 O(n)+O(0.5n)

前面两种的空间准确来讲其实是O(n)+O(1.5n)。通过就地可以进行空间优化。

理论上任何传播算法都可以做到就地，因为每一状态都只与紧邻的前一状态有关。

由于本题的<font color=red>两个</font>传播公式相互耦合，同时实现两个状态的就地传播是不可能的。

可以理解为：当i取值较大时，sum的某一项sum[i]可以传播到f相对很远的两项f[2i],f[2i+1]，为了之后计算sum[2i]和sum[2i+1]，f的两项必须被动态缓存起来。可以预见，最多的缓存项可以达到n/4的规模。

但是，sum和f分别的就地传播，两种方案都可行。如下图所示：

再关注一下递推公式：

f(n) = SUM(n/2)+1,\quad SUM(i) = SUM(i-1)+f(i)

于是我们可以由此写就地传播辣~～

sum就地： O(n)+O(1.0n)
#include <bits/stdc++.h>
using namespace std;

int f[1005], sum;

int main(){
    int n; cin>>n;
    for(int i = 1; i <= n; i++){
        f[i] = sum + 1;
        if(i%2) sum += f[(i+1)/2];
    }
    cout<< f[n];
}
f就地： O(n)+O(0.5n)
#include <bits/stdc++.h>
using namespace std;

int f, sum[505];

int main(){
    int n; cin>>n;
    for(int i = 1; i <= n/2; i++){
        f = sum[i/2] + 1;
        sum[i] = f + sum[i - 1];
    }
    cout<< sum[n/2] + 1;
}

就地+队列 O(0.5n)+O(0.25n)

我们之前已经提到，f可以用动态缓存的方式记录。并且，每一个f[i]的调用都是先进先出的，因此可以采用队列。。

sum只要求到n/2就可以求出f[n]，sum只要求到n/4就可以求出f[n/2]。

因此，sum求到n/4（此时积累了n/4的缓存），然后卸载缓存到f[n/2]求得sum[n/2]，即可求出f[n]。如图：

#include <bits/stdc++.h>
using namespace std;

queue<int> f; int sum = 0; //sum[0] = 0

int main(){
    int n; cin>>n;
    int i;

    f.push(1);  //initialize f as sum[1]
    for(i = 1; i <= (n >> 2); i++){
        sum += f.front(); f.pop();  //reserve f in queue buffer
        f.push(sum+1); f.push(sum+1);
    }
    for(     ; i <= (n >> 1); i++){
        sum += f.front(); f.pop();  //clear the buffer(maybe 1 element left sometime)
    }

    cout<< sum + 1;
}