洛谷 P11500 分析（别看）

科技起源

2026-07-16 10:48:15

发布于：河北

3阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：方案数

1.2 题目背景、允许、禁止与限制

背景：需要为运动员安排训练强度，要求总强度为 $n$ 且第一天强度为 $k$ 的情况下求有多少种训练方案
允许：
禁止：
限制：相邻两天训练强度必须一高一低

1.3 题目数据范围与猜测

$1 \le k \le n \le 5000 \longrightarrow O(nk)$

1.4 一句话概括题意

需要为运动员安排训练强度，要求总强度为 $n$ 且第一天强度为 $k$ 的情况下求有多少种训练方案，要求相邻两天训练强度必须一高一低

2 题目破题推导

2.1 分情况考虑

当连续三天的训练量分别为 $a,b,c$ 时，需要保证 $a < b > c$ 或者 $a > b < c$
那么我们可以假设两种情况：

当今天比昨天多练时，方案数总和就是同时满足昨天所有比今天训练少且昨天比前天训练也少的和
当今天比昨天少练时，方案数总和就是同时满足昨天所有比今天训练多且昨天比前天训练也多的和

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：动态求取方案数 $\longrightarrow$ $\huge{计数dp}$
证明可以使用 $\huge{dp}$

无后效性，因为今天的训练总方案数只和昨天（还有前天）有关，和大前天，大大前天...的训练量都无关
重叠子问题
最优子结构：通过昨天的方案数可以求出准确的今天方案数

但是，如果正常dp，时间复杂度 $O(n^3)$ 会超时

因为我们知道，今天的总方案数是连续的一段，因此在求和时可以用 $\huge{前缀和优化}$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int n, k;
const int N = 5005, M = 2;
int dp[N][N][M];
/*
dp[i][j][0]表示总共训练量为i，今天（最后一天）训练量为j，比昨天少练的方案数
dp[i][j][1]表示总共训练量为i，今天（最后一天）训练量为j，比昨天多练的方案数
*/
const int MOD = 1e9 + 7;
int sum[N][N][M];

int main(){

    cin >> n >> k;
    if (n == k){
        cout << 1;
        return 0;
    }
    dp[k][k][0] = dp[k][k][1] = 1;
    for (int i = 1;i <= n;i++){
        sum[k][i][0] = sum[k][i - 1][0] + dp[k][i][0];
        sum[k][i][0] %= MOD;
        sum[k][i][1] = sum[k][i - 1][1] + dp[k][i][1];
        sum[k][i][1] %= MOD;
    }
    /*
    for (int i = k + 1;i <= n;i++){// 总训练量一定>k,<=n
        for (int j = 1;j < i;j++){// 当前这一天的训练量
            for (int l = j + 1;l <= min(n, i - j);l++){// 昨天比今天多练
                dp[i][j][0] += dp[i - j][l][1];// 如果昨天比今天多练，那也会比前天多练
                dp[i][j][0] %= MOD;
            }
            for (int l = 1;l <= min(j - 1, i - j);l++){// 昨天比今天少练（要么正常j-1，万一j-1超出了范围那么就要变成到i-j）
                dp[i][j][1] += dp[i - j][l][0];// 如果昨天比今天少练，那也会比前天少练
                dp[i][j][1] %= MOD;
            }
        }
    }
    O(n^3),n <= 5000 超时优化
    第三层循环可以用前缀和优化
    */
    for (int i = k + 1;i <= n;i++){
        for (int j = 1;j < i;j++){
            dp[i][j][0] = (sum[i - j][i - 1][1] - sum[i - j][j][1] + MOD) % MOD; 
            dp[i][j][1] = sum[i - j][j - 1][0] % MOD;
        }
        for (int j = 1;j <= n;j++){
            sum[i][j][0] = sum[i][j - 1][0] + dp[i][j][0];
            sum[i][j][0] %= MOD;
            sum[i][j][1] = sum[i][j - 1][1] + dp[i][j][1];
            sum[i][j][1] %= MOD;
        }
    }
    cout << (sum[n][n][0] + sum[n][n][1]) % MOD;
        
    return 0;
}