半数集问题（记忆化搜索）

一开始果断选择暴力做法，结果就炸了。

暴力代码：

#include<bits/stdc++.h>

using namespace std;

long long int ans=1;//因为后面不包括本身，所以计为1

void f(int a){

int mid=a/2;//取中间值

for(int i=1;i<=mid;i++)//将所有可以取的值枚举一遍

{

ans++;

f(i);//选取之后，再进行加数字

}

}

int main()

{

int a;

while(cin>>a){//输入数字

f(a);

cout<<ans<<endl; 

ans=1;//重置

}

return 0;

}

如果仔细观察就知道，之前的数可选取的结果会重复出现.

比如6和12：

6的选取之后的数(因为经过选取，所以不包括本身)有16,26,36,126,136;

12如果前面选取6，即为612；

那么之后的结果就为1612，2612，3612，12612，13612；

其实如果当选取的数一样的话，结果是一样的

只要创建个数组，记录一下所选取的数的结果的多少就可以节约时间了

解题思路:创建个数组，记录一下所选取的数的结果，从1到1000，把所有数先算出来
参考代码:

#include<bits/stdc++.h>

using namespace std;

long long int ans=1;

int m[1000];

int f(int a){

  int mid=a/2;//取中间数 

  for(int i=1;i<=mid;i++)

  {

  if(m[i]==0) ans++,f(i);//如果没有被记录 

  else ans+=m[i];

  }

  return ans;

}

int main()

{

  int a;

memset(m,0,sizeof(m));

  for(int i=1;i<=1000;i++)

{

  m[i]=f(i);//记录下该数的半数集的元素个数 

  ans=1;//重置 

  }

while(cin>>a){

  cout<<m[a]<<endl; 

 }

 return 0;

}