洛谷P1028动规算法
首先我们可以写一个递归
include<bits/stdc++.h>
using namespace std;
long long n;
int main(){
long long f[1001];memset(f,0,sizeof(f));cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i/2;j++){f[i]+=f[j];}f[i]++;}cout<<f[n]<<endl;return 0;
}
稍微修改一下代码，令其输出答案集A，效果如下
1
2
2
4
4
6
6
10
10
14
14
20
20
26
26
36
36
46
46
60
60
74
74
94
94
114
114
观察可知，答案集可以简化为序列B
1 2 4 6 10 14 20 26 36 46
继续观察得，B[i]=b[i+1]/2+b[i-1]
b[i/2+1]=a[i];
代码实现如下：
include<bits/stdc++.h>
using namespace std;
int main()
{
long long a[100000]={0,1,2,4,6,10},n;int nn;
cin>>n;
nn=(n+2)/2;
for(int i=2;i<=nn;i++)
a[i]=a[(i+1)/2]+a[i-1];
cout<<a[nn];
}
版权声明：本文为luotianyi20120712原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。