23568: 幸福的寒假生活

http://cs101.openjudge.cn/practice/23568/

p大计划延长2021-2022学年度的寒假——从1月7日到2月20日共45天。Casper和Emily得知这个消息后非常激动，迫不及待地开始规划起寒假日程，希望能从中获得满满的幸福。

现在，可供Casper选择的有n个浪漫计划，包括开始日期和结束日期，以及通过参加这个计划能得到的幸福值，请计算Casper在这个假期能够获得的最大幸福值。

注意所有参加的计划不能有任何时间上的重叠，在第x天结束的计划和在第x天开始的计划不可同时选择；此外，由于Emily必须在2月21日返校，所以不能参加在2月20日之后结束的计划。

输入

第一行包含一个整数n，表示有n个浪漫计划（n<200）

紧接着的n行，每一行由3个部分组成，首先是第 i 个计划开始的日期 si，然后是结束日期 ei，最后是Casper和Emily在这个计划中能获得的幸福值 vi，以空格分隔。输入保证每个计划的时长都在1天至10天的范围内，且计划的开始日期都在寒假范围内。

输出

输出他们所能获得的最大幸福值

样例输入

Sample Input1:
3
1.18 1.27 100
1.23 1.27 20
2.4 2.8 81

Sample Output1:
181

样例输出

Sample Input2:
5
1.18 1.27 100
1.10 1.19 90
1.23 1.27 20
2.4 2.8 81
2.10 2.23 100

Sample Output2:
191

提示

tag: dp 先把日期映射到[0,44]的区间上，然后利用动态规划算法求解，子问题可以考虑为：前i个计划下所能得到的最大幸福值

来源: 2021fall-cs101, zzr

这个dp需要先做数据预处理，两个考点。

python

# 2023 蒋子轩
def date_to_index(date):
    month,day=map(int,date.split('.'))
    return (month-1)*31+day-6
data=[]
dp=[0]*46
n=int(input())
for _ in range(n):
    start,end,happiness=input().split()
    start,end,happiness=date_to_index(start),date_to_index(end),int(happiness)
    data.append((start,end,happiness))
for i in range(1,46):
    dp[i]=dp[i-1]
    for start,end,happiness in data:
        if end==i:
            dp[i]=max(dp[i],dp[start-1]+happiness)
print(dp[-1])

下面给出一个更清晰、更高效的版本，保留逻辑本质（DP + 日期映射），并进行如下优化：

✅ 优化点说明

预处理排序：只按结束日期排序，减少无谓遍历。
日期映射更直观：用一个字典映射日期 → 第几天（0~44）。
DP转移高效：利用二分查找（bisect_right）快速找到不冲突的上一个计划。

python

from bisect import bisect_right

# 建立日期到 [0,44] 映射
def date_to_index(date):
    month, day = map(int, date.split('.'))
    return (month - 1) * 31 + day - 7  # 1.7 -> 0, 2.20 -> 44

n = int(input())
plans = []

for _ in range(n):
    s, e, v = input().split()
    s, e, v = date_to_index(s), date_to_index(e), int(v)
    if e <= 44:  # 不能超过 2.20
        plans.append((s, e, v))

# 按结束时间排序
plans.sort(key=lambda x: x[1])

# dp[i]: 前 i 个计划可获得的最大幸福值
dp = [0] * (len(plans) + 1)
ends = [p[1] for p in plans]  # 用于二分查找前一个不重叠计划

for i in range(1, len(plans) + 1):
    s, e, v = plans[i - 1]
    # 找到最后一个 end < s 的计划位置
    j = bisect_right(ends, s - 1)
    # 两种选择：不选第 i 个 或 选第 i 个
    dp[i] = max(dp[i - 1], dp[j] + v)

print(dp[-1])

代码解析

步骤	说明
`date_to_index`	将日期转成 0~44 的整数索引（1.7→0，2.20→44）
过滤条件	确保计划不超过寒假（`e<=44`）
排序	按 `end` 排序，方便 DP
`bisect_right`	在已结束计划中找到上一个不冲突的计划
转移	`dp[i] = max(dp[i-1], dp[j] + v)`，标准加权区间调度

复杂度分析

日期映射：O(n)
排序：O(n log n)
二分查找 + DP：O(n log n)

python

# 映射到 0..44，并用 O(n^2) DP（n < 200 足够）
def date_to_index(date_str):
    month, day = map(int, date_str.split('.'))
    # 把 1.7 -> 0，1.8 -> 1, ..., 2.20 -> 44
    # 计算方法：如果把每月按 31 天简单铺开，再减去 7
    return (month - 1) * 31 + day - 7

n = int(input().strip())
plans = []
for _ in range(n):
    s_str, e_str, v_str = input().split()
    s_idx = date_to_index(s_str)
    e_idx = date_to_index(e_str)
    v = int(v_str)
    # 严格要求结束不在假期后（不能在 2.20 之后结束）
    if e_idx <= 44:
        plans.append((s_idx, e_idx, v))

# 如果没有合法计划
if not plans:
    print(0)
    exit()

# 按结束时间排序
plans.sort(key=lambda x: x[1])

m = len(plans)
dp = [0] * m
ans = 0
for i in range(m):
    s_i, e_i, v_i = plans[i]
    # 选第 i 个，初始为它自己的价值
    best = v_i
    # 在前面的计划中找不冲突（结束 < s_i）的最大 dp
    for j in range(i):
        s_j, e_j, v_j = plans[j]
        if e_j < s_i:          # 严格不相交（结束日不能等于开始日）
            best = max(best, dp[j] + v_i)
    dp[i] = max(dp[i-1], best) if i > 0 else best
    ans = max(ans, dp[i])

print(ans)

23568: 幸福的寒假生活 ​

23568: 幸福的寒假生活