B3636 文字工作——题解

解题思路

令 f[i] 表示得到 $i$ 个字的最少次数。最后一步若是增加一个字，则来自 $i-1$；若 $i$ 为偶数，最后一步也可能是复制粘贴，来自 $i/2$。取两种转移的较小值。

复杂度分析

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int f[1000005];
int main(){
    int n;cin>>n;f[1]=0;
    for(int i=2;i<=n;i++){f[i]=f[i-1]+1;if(i%2==0)f[i]=min(f[i],f[i/2]+1);}
    cout<<f[n]<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int f[1000005]; int main(){ int n;cin>>n;f[1]=0; for(int i=2;i<=n;i++){f[i]=f[i-1]+1;if(i%2==0)f[i]=min(f[i],f[i/2]+1);} cout<<f[n]<<'\n';return 0; }