T30911: 多少人知道秘密

dp, http://cs101.openjudge.cn/practice/30911/

在第 1 天，有一个人发现了一个秘密。给你一个整数 delay ，表示每个人会在发现秘密后的第delay 天及以后，每天将秘密告诉给一个新人。同时给你一个整数 forget ，表示每个人在发现秘密的后的第 forget 天及之后会忘记这个秘密。一个人不能在忘记秘密那一天及之后的日子里把秘密告诉别人。
给你一个整数 n ，请计算第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 1000000007取余后输出。
输入
一行，包括三个整数n,delay和forget ( 1 <= n <= 100)
输出
第 n 天结束时，知道秘密的人数对1000000007取余后的结果。
样例输入
#输入样例1
4 1 3
#输入样例2
90 3 9
样例输出
#输出样例1
6
#输出样例2
386701165
提示
对样例1的解释：第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）第 2 天：A 把秘密分享给 B 。（两个人知道秘密）第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）

这是一个经典的动态规划（Dynamic Programming）问题。可以通过维护每天“新知道秘密的人数”来解决。

算法思路

设 dp[i] 表示在第 i 天新发现/得知秘密的人数。

初始状态：第 1 天只有 1 个人知道秘密，所以 dp[1] = 1。
状态转移：对于第 i 天（ $i > 1$ ），新得知秘密的人是由之前已经知道秘密、且处于“可以分享秘密”阶段的人分享而来的。
- 一个人在第 j 天得知秘密后，他能够分享秘密的区间是：从第 j + delay 天开始，到第 j + forget - 1 天结束。
- 反过来，在第 i 天，能够分享秘密的人必须是在第 j 天得知秘密的，其中满足： $i - forget < j \leq i - delay$ 。
- 因此，第 i 天新得知秘密的人数： $d p [i] = \sum_{j = max (1, i - forget + 1)}^{i - delay} d p [j]$
计算第 n 天结束时知道秘密的总人数：
- 只有在第 j 天得知秘密，且到第 n 天还没有忘记的人才算在内。
- 满足未忘记的条件是： $j + forget > n ⟹ j > n - forget$ 。
- 所以最终人数为： $Total = \sum_{j = max (1, n - forget + 1)}^{n} d p [j]$
- 每次累加时需要对 $1000000007$ 取模。

Python 3 实现代码

python

import sys

def solve():
    # 读取所有输入
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    delay = int(input_data[1])
    forget = int(input_data[2])
    
    MOD = 1000000007
    
    # dp[i] 表示第 i 天新知道秘密的人数
    dp = [0] * (n + 1)
    dp[1] = 1
    
    for i in range(2, n + 1):
        # 能在第 i 天分享秘密的人，其得知秘密的日期 j 需满足：
        # i - forget < j <= i - delay
        start = max(1, i - forget + 1)
        end = i - delay
        
        current_shares = 0
        # # 如果 start > end，这里会自动跳过，不影响结果
        for j in range(start, end + 1):
            current_shares = (current_shares + dp[j]) % MOD
        dp[i] = current_shares
        
    # 计算在第 n 天结束时，还没忘记秘密的人数之和
    # 还没忘记秘密的人，其得知秘密的日期 j 需满足：
    # j + forget > n  =>  j >= n - forget + 1
    total_knowing = 0
    start = max(1, n - forget + 1)
    for j in range(start, n + 1):
        total_knowing = (total_knowing + dp[j]) % MOD
        
    print(total_knowing)

if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：对于每一天 $i$ ，我们需要累加长度最多为 $forget$ 的区间。由于 $n \leq 100$ ，双重循环的最大计算量约为 $100 \times 100 = 10^{4}$ 次操作，运行时间远低于 1000ms 限制。
空间复杂度：使用了大小为 $n + 1$ 的 dp 数组，空间复杂度为 $O (n)$ ，在 $n \leq 100$ 的情况下消耗内存极少，符合 65536kB 的限制。

T30911: 多少人知道秘密 ​

T30911: 多少人知道秘密