题解 P5810 【[SCOI2004]文本的输入】

1. 这里提供记忆化搜索做法。

2. 转移方程为$dp[i]=\underset{j|i}{min}(dp[j]+3+2\ast \frac{i}{j})$. 每一次转移使用试除法复杂度为$O(\sqrt{n})$.

3. 关于答案位置的离散性，本人亲测最大到 $n+n/4$ 即可通过本题，不需要开到$2\ast n$.

4. 总复杂度为$O(n\sqrt{n})$.

#include <bits/stdc++.h>
using namespace std;
int mem[50100];
int n;
int dfs(int now){
  if(!now) return 0;
  if(mem[now]) return mem[now];
  int minn=1e9;
  minn=min(minn,dfs(now-1)+1);
  for(int i=2;i*i<=now;i++)
     if(now%i==0){
        minn=min(minn,dfs(i)+3+2*(now/i));
        minn=min(minn,dfs(now/i)+3+2*i);
     }
  return mem[now]=minn;
}
int main(){
  cin>>n;
  dfs(n+n/4);
  int ans=1e9;
  for(int i=n;i<=n+n/4;i++) ans=min(ans,dfs(i));
  cout<<ans;
  return 0;
}