原题链接
1 题目
1.1 题目所需求出内容
对于本题,最终要求:方案数
1.2 题目背景、允许、禁止与限制
背景:需要为运动员安排训练强度,要求总强度为 nnn 且第一天强度为 kkk 的情况下求有多少种训练方案
允许:
禁止:
限制:相邻两天训练强度必须一高一低
1.3 题目数据范围与猜测
1≤k≤n≤5000⟶O(nk)1 \le k \le n \le 5000 \longrightarrow O(nk)1≤k≤n≤5000⟶O(nk)
1.4 一句话概括题意
需要为运动员安排训练强度,要求总强度为 nnn 且第一天强度为 kkk 的情况下求有多少种训练方案,要求相邻两天训练强度必须一高一低
2 题目破题推导
2.1 分情况考虑
当连续三天的训练量分别为 a,b,ca,b,ca,b,c 时,需要保证 a<b>ca < b > ca<b>c 或者 a>b<ca > b < ca>b<c
那么我们可以假设两种情况:
* 当今天比昨天多练时,方案数总和就是同时满足昨天所有比今天训练少且昨天比前天训练也少的和
* 当今天比昨天少练时,方案数总和就是同时满足昨天所有比今天训练多且昨天比前天训练也多的和
3 模型匹配
> 格式为:"关键词:...... ⟶\longrightarrow⟶ ......\huge{......}......"
关键词:动态求取方案数 ⟶\longrightarrow⟶ 计数dp\huge{计数dp}计数dp
证明可以使用 dp\huge{dp}dp
1. 无后效性,因为今天的训练总方案数只和昨天(还有前天)有关,和大前天,大大前天...的训练量都无关
2. 重叠子问题
3. 最优子结构:通过昨天的方案数可以求出准确的今天方案数
但是,如果正常DP,时间复杂度 O(N3)O(N^3)O(N3) 会超时
因为我们知道,今天的总方案数是连续的一段,因此在求和时可以用 前缀和优化\huge{前缀和优化}前缀和优化
4 最终代码(禁止抄袭,仅用于参考)