洛谷 1028. P1028 [NOIP2001 普及组] 数的计算
原题链接
简单
作者:
蓬蒿人
,
2024-02-18 17:54:15
,
所有人可见
,
阅读 29
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
// 注意要通过100%的数据的话就要 高精度计算
// 只要开三个vector数组存储 不断循环计算下去就好了
// 一个是当前值 另外是前一个位置的和前二个位置的
int n;
int f[1010];
// f[1]=1 1
// f[2]=2 {2,2 1}
// f[3]=2 {3,2 1}
// f[4]=4 {4,4 2,4 1,4 2 1}
// f[5]=4 {5,5 2,5 1,5 2 1}
// f[6]=6 {6,6 3,6 2,6 1,6 3 1,6 2 1}
// 可以观察到f[n]=f[1]+..+f[n/2]+1
void slove() {
cin>>n;
f[1]=1;
for (int i=2;i<=n;i++) {
for (int j=0;j<=i/2;j++) {
f[i]+=f[j];
}
f[i]+=1;
//printf ("f[%d]=%d \n",i,f[i]);
}
cout<<f[n];
return ;
}
int main () {
slove();
return 0;
}