zoj 1539 Lot 简单DP 记忆化

Lot


Time Limit: 2 Seconds      Memory Limit: 65536 KB

Out of N soldiers, standing in one line, it is required to choose several to send them scouting.
In order to do that, the following operation is performed several times: if the line consists of more than three soldiers, then all soldiers, standing on even positions, or all soldiers, standing on odd positions, are taken away. The above is done until three
or less soldiers are left in the line. They are sent scouting. Find, how many different groups of three scouts may be created this way.

Note: Groups with less than three number of soldiers are not taken into consideration.

0 < N <= 10 000 000

Input

The input file contains the number N.

Process to the end of file.

Output

The output file must contain the solution - the amount of variants.

Sample Input

10
4

Sample Output

2
0

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int f[10000001];
int _find(int v)
{
if(v<3) return f[v]=0;
if(v==3) return f[v]=1;
if(f[v]>0) return f[v];
if(v%2==0) return f[v]=_find(v/2)*2;
else return f[v]=_find(v/2)+_find(v/2+1);
}
int main()
{
int n,s;
while(cin>>n)
{
s=_find(n);
if(s>0)
printf("%d\n",s);
else printf("0\n");
}
return 0;
}
上一篇:气候经济学能发Nature,Science的三大热点问题!


下一篇:CentOS7利用systemctl添加自定义系统服务【转】