题目分析

题意简述

本题存在多组测试用例，每组输入包含三个整数 $n$、$m$、$k$ 以及两个分隔字符。当输入的 $n$ 为 $-1$ 时，程序结束。对于每组有效输入，模拟一个生物数量变化的过程，最终输出在第 $k$ 时刻生物的总数。

输入

• 多组测试用例，每组格式为 $n$、分隔字符、$m$、分隔字符、$k$。
• 当 $n$ 为 $-1$ 时，停止输入。

输出

对于每组有效输入，输出格式为 $n$, $m$, $k$: 生物总数。

解题思路

动态规划数组初始化

定义一个二维数组 $q[50][50]$ 来记录不同时刻不同等级生物的数量，初始时 $q[1][1] = 1$，意味着在第 $1$ 时刻，等级为 $1$ 的生物数量为 $1$。

生物数量递推

使用循环从第 $2$ 时刻开始，递推计算每个时刻不同等级生物的数量：

1. 对于等级 $liv$（$2 \leq liv \leq n$ 且 $liv \leq t$），$q[t][liv] = q[t - 1][liv - 1]$，表示每个等级的生物会在下一步提升一个等级。
2. 计算当前时刻提升等级生物的总数 $sum$，若 $sum \leq 100$，则计算新出生的生物数量 $born$：
   • 新出生生物数量 $born$ 由等级为 $7$ 和 $8$ 的生物数量以及特定等级（与 $m$ 有关）的生物数量决定。当 $m = 1$ 时，仅考虑等级为 $9$ 的生物；当 $m \neq 1$ 时，考虑等级为 $9$ 和 $10$ 的生物。
   • 新出生的生物等级为 $1$，即 $q[t][1] = born$。

结果计算

在第 $k$ 时刻，遍历所有等级 $lv$（$1 \leq lv \leq n$ 且 $lv \leq k$），将 $q[k][lv]$ 累加得到生物总数 $s$，并输出结果。

代码实现

#include <iostream>
#include <vector>
using namespace std;

void simulate(int n, int m, int k) {
    vector<int> age_counts(n + 1, 0); // 索引1到n表示1到n个月的老鼠
    age_counts[1] = 1; // 初始1对新生鼠
    
    for (int month = 2; month <= k; ++month) {
        vector<int> new_age_counts(n + 1, 0);
        int total = 0;
        
        // 统计上个月总数，决定是否保留新生鼠
        for (int age = 1; age <= n; ++age) {
            total += age_counts[age];
        }
        
        // 处理存活的老鼠：年龄增加1个月
        for (int age = 1; age < n; ++age) {
            new_age_counts[age + 1] = age_counts[age];
        }
        
        // 计算新生鼠数量
        int newborns = 0;
        for (int age = 7; age <= n; ++age) {
            if (age <= 8) {
                newborns += age_counts[age];
            } else if (age <= 8 + m) {
                newborns += 2 * age_counts[age];
            }
        }
        
        // 根据总数决定是否保留新生鼠
        if (total <= 100) {
            new_age_counts[1] = newborns;
        }
        
        age_counts = new_age_counts;
    }
    
    // 计算第k个月的总数
    int total = 0;
    for (int age = 1; age <= n; ++age) {
        total += age_counts[age];
    }
    
    cout << n << "," << m << "," << k << ": " << total << endl;
}

int main() {
    int n, m, k;
    char comma;
    while (true) {
        cin >> n;
        if (n == -1) break;
        cin >> comma >> m >> comma >> k;
        simulate(n, m, k);
    }
    return 0;
}

代码说明

1. 输入处理

   • 使用 while (1) 循环持续读取输入，当输入的 $n$ 为 $-1$ 时，通过 if (!(~n)) break; 终止循环。
   • 读取分隔字符和 $m$、$k$。

2. 动态规划数组初始化

   • 定义二维数组 $q[50][50]$ 并初始化为 $0$，将 $q[1][1]$ 设为 $1$。

3. 生物数量递推

   • 使用外层循环 for (int t = 2; t <= k; t++) 遍历每个时刻。
   • 内层循环 for (int liv = 2; liv <= n && liv <= t; liv++) 计算每个时刻不同等级生物的数量。
   • 根据 $sum$ 的值和 $m$ 的值计算新出生生物的数量 $born$，并更新 $q[t][1]$。

4. 结果计算与输出

   • 遍历所有等级，将 $q[k][lv]$ 累加得到生物总数 $s$。
   • 输出 $n$, $m$, $k$: 生物总数。