洛谷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];

}

UPDATE

2019.5.11

测试一下博客

巴特西

洛谷P1028动规算法

最新文章

热门文章