数的计数(noip2001,动态规划递推)

题目链接:

普通版:

https://www.luogu.org/problemnew/show/P1028

数据加强版:

https://www.luogu.org/problemnew/show/P2240

中间插一段,奇怪了,我明明想到的是最好的那种递推方法,结果写着写着忘记了,写成最差的递推方法

所以中间插一段被我遗忘的好方法

这个也是这题的书上的答案

#include<bits/stdc++.h>

using namespace std;

int a[];

int main()

{

    int n;

    cin>>n;

    a[]=;

    for(int i=;i<=n;i++)

    {

        a[i]=a[i-];

        if(i%==)

            a[i]=a[i-]+a[i/];

    }

    cout<<a[i];

    return ;

}

稍微解释一下:

举个例子就好了

a[5]=a[4]

a[6]=a[5]+a[6/3],那个a[6/3]就是a[3],因为相对于a[4]来说a[6]多了个a[3]的全部子数字

因为a[4]只能分解1~2

a[5]同a[4]一样

而a[6]可以分解1~3

所以a[6]多个a[3]

以下为自己写的垃圾方法:

基本思路:

@1:基本递推:

第n个数,它产生n/2个新的数,由于1~n/2都小于n,所以可以用递推,都计算到n了那么1~n/2的值肯定都已知了

@2:边缘条件:

我们把n=1和n=0时结果都为1都一开始就初始化好,作为初始条件

@3:细节

ps:这个地方好像有更好的办法而不是用奇葩的+1法,可是我懒得想了

在具体的数组中,a[n]应该是不包括n本身的所有子数字数目,为什么不能包括本身呢,因为后面要通过前面的数据递推

比如说a[6]=6/2 +a[1] + a[2] +a[3],那么其实是a[6]= 1+a[1] + 1+a[2] + 1+a[3],所以最后都要加回来

@4:规律

这个结果有奇偶的规律,比如说n=3与n=2结果相同,n=19与n=18结果相同,也就是只要计算一半就好了

AC代码(普通版和数据加强版都适用)

#include<bits/stdc++.h>

using namespace std;

int a[];

int main()

{

    std::ios::sync_with_stdio(false);

    int n;cin>>n;

    if(n<=)

    {

        cout<<+<<endl;

        return ;

    }

    else

    {

        for(int i=;i<=n+;i++)

        {

            if(i%==)

            {

                a[i]=i/;

                for(int j=;j<=i/;j++)

                    a[i]+=a[j];

            }

            else

                a[i]=a[i-];

        }

    }

    if(n%==)

        cout<<a[n]+<<endl;

    else

        cout<<a[n/*]+<<endl;

}

巴特西

数的计数(noip2001,动态规划递推)

ps:这个地方好像有更好的办法而不是用奇葩的+1法,可是我懒得想了

最新文章

热门文章