CodeVS/1011

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
数的计算(NOIP2001)	★☆☆☆☆	答案正确	100	2014/10/02 23:14:02	变量打错（75）

题意

原题描述本来就很裸了，但是要特别注意下第三点：按规则处理，所谓原数的一半是指最开始的n而不是后来得到的数。

其它就按原题理解应该没什么问题。

题解

题目的分类是递推，那就从递推说起。递推式容易得到：

f[1]=1;
f[n]=f[1]+f[2]+...+f[n/2]+1;

从1循环到n就好，由于测试数据较水两层循环的版本已经可以AC了，。（当然毕竟是01年的题目用现在的机器跑....）

递推的最简单优化方式就是再加一个数组记录前n项和优化，可以优化到。

递推就不写了。

接下来是搜索，暴搜也能过，然后优化可以加一个数组存储最优值，记忆化搜索，详见代码。

代码

1011搜索.cpp代码已折叠 展开折叠内容
#include<iostream> using namespace std; int dfs(int n) { int c=0; if(n==1) return 0; for(int i=1;i<=(n>>1);++i) c+=dfs(i)+1; return c; } int main() { int n=0; cin>>n; cout<<dfs(n)+1; return 0; }

1011记忆化搜索.cpp代码已折叠 展开折叠内容
#include<iostream> using namespace std; int c[1001]={}; int dfs(int n) { if(n==1) return 0; for(int i=1;i<=(n>>1);++i) { if(c[i])c[n]+=c[i]+1; else c[n]+=dfs(i)+1; } return c[n]; } int main() { int n=0; cin>>n; cout<<dfs(n)+1; return 0; }