求救 分组问题

常规
1 
5.  分组问题
题目ID：7707
时间限制: 1000ms
空间限制: 262144kB
题目描述
有n个人站成一排，编号为1-n，现在将他们分成多组，每组的人的编号都是连续的(如3,4,5是连续的;1,3不是连续的)，且每组的人数为1或2。问有几种分发

输入格式
输入一个整数n

输出格式
按题目描述输出

样例
Input 1
4
Output 1
5
样例解释
将4个人分为两组，每组有两个人的方式有两种（1和2，3和4），每组有一个人的方式有两种（1，2，3和4），总共有5种方式。

数据范围
N<=5000
2 个赞
2

有人会写吗

2 个赞
3

高精度

1 个赞
4

斐波那契数列

1 个赞
5 
#include<bits/stdc++.h>
using namespace std;
int f[5055];
int main(){
    int n;
    cin>>n;
    f[1]=1;
    f[2]=2;
    for(int i=3;i<=n;i++){
      f[i]=f[i-1]+f[i-2];
    }
    cout<<f[n];
    return 0;
}
WA 0分啊
1 个赞
6

高精度

8

？？？
说话文明一点

1 个赞
9

不会高精度？大不了用Python

要解决这个问题，我们可以使用动态规划。题目的核心是如何将一排人以连续的方式分成不同的组，每组可以由1或2个人组成。我们可以定义一个数组 dp，其中 dp[i] 表示将前 i 个人分组的方式数。

动态规划状态转移方程

  1. 基础情况：
  • 当 n = 1，只有一个人，可以形成的分组方式为1，即 dp[1] = 1。
  • 当 n = 2，可以有两种分组方式：一个组包含两个（1, 2）或者两个单独的组（1）和（2），即 dp[2] = 2。
  1. 状态转移：
  • 对于 i > 2，我们可以考虑最后一组的情况：
    • 如果最后一个组只包含1人，那么前面 i-1 个人的分组方式为 dp[i-1]。
    • 如果最后一个组包含2人，那么前面 i-2 个人的分组方式为 dp[i-2]。
  • 综合以上两种情况，我们得到：
    • dp[i] = dp[i-1] + dp[i-2]

这种转移方式与斐波那契数列的定义相似，因此可以使用一维数组来进行填充。

实现

以下是核心代码：

// 定义一个用于高精度的大整数类
class BigInt {
public:
    vector<int> digits; // 存储每一位数字
    BigInt() { digits.push_back(0); } // 初始化为0

    // 从字符串构造
    BigInt(const string& s) {
        for (int i = s.length() - 1; i >= 0; i--) {
            digits.push_back(s[i] - '0');
        }
    }

    // 加法
    BigInt operator+(const BigInt& other) const {
        BigInt result;
        int carry = 0;
        int maxLength = max(digits.size(), other.digits.size());

        for (int i = 0; i < maxLength || carry; i++) {
            if (i == result.digits.size()) {
                result.digits.push_back(0);
            }
            if (i < digits.size()) {
                result.digits[i] += digits[i];
            }
            if (i < other.digits.size()) {
                result.digits[i] += other.digits[i];
            }
            result.digits[i] += carry;
            carry = result.digits[i] / 10;
            result.digits[i] %= 10;
        }
        return result;
    }

    // 输出
    void print() const {
        for (int i = digits.size() - 1; i >= 0; i--) {
            cout << digits[i];
        }
        cout << endl;
    }
};

代码解释

  1. BigInt 类：我创建了一个 BigInt 类，该类使用一个 digits 向量来存储大整数的每一位。实现了加法操作符的重载，以支持与其他大整数的相加。
  2. 构造函数：可以从字符串构造 BigInt 对象，便于在处理大数字时直接从字符串转换。
  3. 加法：在加法操作中，我们处理每一位数字并考虑进位。
  4. 主函数：与前面的动态规划相同，初始化 dp 数组并计算每种分组方式数量。每次计算都使用 BigInt 的加法。
  5. 输出：通过 print 方法输出最终的结果。
主函数应该会吧…… 
    int n;
    cin >> n;

    if (n == 0) {
        cout << "0" << endl;
        return 0;
    }

    // dp[i]表示分组的方式数，使用高精度 BigInt
    vector<BigInt> dp(n + 1);
    
    // 边界条件
    dp[1] = BigInt("1"); // 1个学生，1种方法
    if (n > 1) {
        dp[2] = BigInt("2"); // 2个学生，2种方法
    }

    // 填充dp数组
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    // 输出结果
    dp[n].print();
10

我突然发现一个问题

11

这个直接上斐波那契数列就可以了欸

12

不过也感谢你给我一个看不懂的东东

13

:sweat_smile: :rofl: :joy:

14

估计 @叶景润 看到后会直接红温。。。 :sweat_smile: :rofl: :joy:

15

说到底我还是用斐波那契数列A了

16

:grinning: :grinning: :grinning: