P1028

　　一开始没看懂题，看了题解才明白的 = =。思路是，先找规律，会发现有重合部分，利用这些重合部分，写出递推公式。

　　num = 0 时，只有 1 种组合；

　　num = 1 时，只有 1 种组合；

　　num = 2 时，有 12, 2 两种组合；

　　num = 3 时，有 13, 3 两种组合（不能超过原数的一半）；

　　num = 4 时，有 124, 24, 14, 4 四种组合；

　　...

　　如此下去，会发现 num 为奇数时等于 num - 1 的结果，而最基本的部分 num = 0, num = 1 是明确的。

　　写出递推式：

$$ f[i] = \left\{\begin{aligned} 1 &\quad i = 1; \\ f[i/2] + f[i - 1] &\quad i \ is \ even; \\ f[i - 1] &\quad i \ is \ odd. \end{aligned} \right. $$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < b; i++)

#define min(a, b) ((a) < (b) ? (a) : (b))

#define max(a, b) ((a) > (b) ? (a) : (b))

#define index(a) (a - 'A')

#define transUpp(a) (a - 32)

#define transLow(a) (a + 32)

#define ll long long

#define PB push_back

int gcd(int a, int b){return b == 0 ? a : gcd(a%b, a);}

const int N = 100010;

int main()

{

    int f[N], num;

    cin >> num;

    f[0] = 1;

    for (int i = 1; i <= num; i++)

        f[i] = ((i + 1) & 1) * f[i >> 1] + f[i - 1];

    cout << f[num] << endl;

    return 0;

}

巴特西

P1028

最新文章

热门文章