题解：洛谷 P2098 [USACO16DEC] Team Building P

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

---

【题目来源】

洛谷：P2098 [USACO16DEC] Team Building P - 洛谷

【题目描述】

每年，Farmer John 都会带着他的N NN头奶牛参加州展览会的“最佳展示”比赛。他的劲敌 Farmer Paul 也会带着他的M MM头奶牛参加比赛（1 ≤ N ≤ 1000 , 1 ≤ M ≤ 1000 1 \leq N \leq 1000, 1 \leq M \leq 10001≤N≤1000,1≤M≤1000）。

参加比赛的N + M N + MN+M头奶牛每头都会获得一个单独的整数得分。然而，今年的最终比赛将由K KK头奶牛组成的团队决定（1 ≤ K ≤ 10 1 \leq K \leq 101≤K≤10），规则如下：

Farmer John 和 Farmer Paul 各自选择K KK头奶牛组成团队进行比赛。这两个团队的奶牛将按得分高低配对：

FJ 团队中得分最高的奶牛与 FP 团队中得分最高的奶牛配对，FJ 团队中得分第二高的奶牛与 FP 团队中得分第二高的奶牛配对，依此类推。如果在每一对中，FJ 的奶牛得分都更高，那么 FJ 获胜。

请帮助 FJ 计算他和 FP 可以选择团队的不同方式的数量，使得 FJ 能够赢得比赛。也就是说，每个不同的（FJ 的K KK头奶牛集合，FP 的K KK头奶牛集合）对，只要 FJ 获胜，都应被计入。输出结果对1 000 000 009 1\,000\,000\,0091000000009取模。

【输入】

输入的第一行包含N NN、M MM和K KK。K KK的值不会超过N NN或M MM。

第二行包含 FJ 的N NN头奶牛的得分。

第三行包含 FP 的M MM头奶牛的得分。

【输出】

输出 FJ 和 FP 可以选择团队的方式数量，使得 FJ 获胜，结果对1 000 000 009 1\,000\,000\,0091000000009取模。

【输入样例】

10 10 3 1 2 2 6 6 7 8 9 14 17 1 3 8 10 10 16 16 18 19 19

【输出样例】

382

【核心思想】

1. 问题分析：FJ 有N NN头奶牛，FP 有M MM头奶牛，各自选择K KK头组成团队。两团队的奶牛按得分从高到低一一配对，若每一对中 FJ 的奶牛得分都严格大于 FP 的奶牛得分，则 FJ 获胜。求 FJ 和 FP 选择团队的不同方式数量（对10 9 + 9 10^9 + 9109+9取模）。这是一个三维线性DP + 容斥原理问题。

2. 算法选择：

   • 降序排序（Descending Sort）：将 FJ 和 FP 的得分分别按降序排序，使得a [ i ] a[i]a[i]和b [ j ] b[j]b[j]分别是当前考虑范围内的最小元素
   • 三维DP（3D Dynamic Programming）：d p [ i ] [ j ] [ k ] dp[i][j][k]dp[i][j][k]表示从 FJ 的前i ii头奶牛和 FP 的前j jj头奶牛中，选出k kk对且 FJ 每对都获胜的方案数
   • 容斥原理（Inclusion-Exclusion Principle）：在状态转移时，用容斥原理处理"不选 FJ 的第i ii头"和"不选 FP 的第j jj头"两种情况的重复计数问题

3. 关键步骤：

   • 初始化：
     • 读入N NN、M MM、K KK，以及 FJ 的得分数组a [ 1.. N ] a[1..N]a[1..N]和 FP 的得分数组b [ 1.. M ] b[1..M]b[1..M]
     • sort(a + 1, a + n + 1, greater<int>())：FJ 得分降序排序
     • sort(b + 1, b + m + 1, greater<int>())：FP 得分降序排序
     • 边界条件：d p [ i ] [ j ] [ 0 ] = 1 dp[i][j][0] = 1dp[i][j][0]=1（对于所有0 ≤ i ≤ N 0 \leq i \leq N0≤i≤N、0 ≤ j ≤ M 0 \leq j \leq M0≤j≤M，选0 00对的方案数为1 11）
   • 状态转移（枚举团队大小k kk从1 11到K KK）：
     • 枚举i ii从k kk到N NN（FJ 至少需要k kk头）
     • 枚举j jj从k kk到M MM（FP 至少需要k kk头）
     • 容斥转移（先计算不考虑a [ i ] a[i]a[i]和b [ j ] b[j]b[j]的方案数）：
       • d p [ i ] [ j ] [ k ] = d p [ i − 1 ] [ j ] [ k ] dp[i][j][k] = dp[i-1][j][k]dp[i][j][k]=dp[i−1][j][k]（不选 FJ 的第i ii头）
       • d p [ i ] [ j ] [ k ] + = d p [ i ] [ j − 1 ] [ k ] dp[i][j][k] += dp[i][j-1][k]dp[i][j][k]+=dp[i][j−1][k]（不选 FP 的第j jj头）
       • d p [ i ] [ j ] [ k ] − = d p [ i − 1 ] [ j − 1 ] [ k ] dp[i][j][k] -= dp[i-1][j-1][k]dp[i][j][k]−=dp[i−1][j−1][k]（容斥去重，两者都不选的情况被重复计算）
       • 注意取模：( x + m o d ) % m o d (x + mod) \% mod(x+mod)%mod防止负数
     • 配对转移（若a [ i ] > b [ j ] a[i] > b[j]a[i]>b[j]，可将它们作为第k kk对）：
       • d p [ i ] [ j ] [ k ] + = d p [ i − 1 ] [ j − 1 ] [ k − 1 ] dp[i][j][k] += dp[i-1][j-1][k-1]dp[i][j][k]+=dp[i−1][j−1][k−1]（从前i − 1 i-1i−1和j − 1 j-1j−1中选k − 1 k-1k−1对，再加上当前这对）
   • 输出答案：d p [ N ] [ M ] [ K ] dp[N][M][K]dp[N][M][K]（从全部N NN头和M MM头中选K KK对的方案数）

4. 时间/空间复杂度：

   • 时间复杂度：O ( N × M × K ) O(N \times M \times K)O(N×M×K)，三维枚举，K ≤ 10 K \leq 10K≤10，N , M ≤ 1000 N, M \leq 1000N,M≤1000
   • 空间复杂度：O ( N × M × K ) O(N \times M \times K)O(N×M×K)，三维DP数组，可通过滚动数组优化至O ( N × M ) O(N \times M)O(N×M)

5. 三维DP + 容斥原理的核心思想：

   • 降序排序的妙处：排序后a [ i ] a[i]a[i]和b [ j ] b[j]b[j]是当前考虑范围内的最小值。若a [ i ] > b [ j ] a[i] > b[j]a[i]>b[j]，则对于任意p ≤ i p \leq ip≤i、q ≤ j q \leq jq≤j都有a [ p ] ≥ a [ i ] > b [ j ] ≥ b [ q ] a[p] \geq a[i] > b[j] \geq b[q]a[p]≥a[i]>b[j]≥b[q]，保证配对的单调性
   • 容斥去重技巧：在计算"从[ 1.. i ] [1..i][1..i]和[ 1.. j ] [1..j][1..j]中选k kk对"时，直接考虑"不选a [ i ] a[i]a[i]"和"不选b [ j ] b[j]b[j]"会重复计算"两者都不选"的情况，因此需要减去d p [ i − 1 ] [ j − 1 ] [ k ] dp[i-1][j-1][k]dp[i−1][j−1][k]
   • 配对条件的处理：只有在a [ i ] > b [ j ] a[i] > b[j]a[i]>b[j]时才允许将a [ i ] a[i]a[i]和b [ j ] b[j]b[j]配成一对，保证 FJ 获胜。由于降序排列，当前这对的 FJ 奶牛是剩余中最弱的，若能赢过 FP 最弱的，则前面所有配对也一定满足条件
   • 三维状态设计：d p [ i ] [ j ] [ k ] dp[i][j][k]dp[i][j][k]同时记录 FJ 前i ii头、FP 前j jj头、已选k kk对三个维度，保证状态无后效性
   • 适用于组合计数、匹配方案数、带约束的选对方案类问题

【算法标签】

#普及+ #线性DP-一维

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将 int 定义为 long long，防止模运算溢出constintN=1005,mod=1e9+9;// N: 最大奶牛数量, mod: 模数intn,m,K;// n: FJ的奶牛数, m: FP的奶牛数, K: 团队大小inta[N],b[N];// a[i]: FJ第i头奶牛的得分, b[i]: FP第i头奶牛的得分// dp[i][j][k]: 从FJ的前i头奶牛和FP的前j头奶牛中，选出k对使得FJ每对都获胜的方案数// 注意：a和b已按降序排序，所以a[i]是FJ前i头中最小的，b[j]是FP前j头中最小的intdp[N][N][15];signedmain()// 使用 signed 替代 int，因为 #define int long long{cin>>n>>m>>K;// 读入FJ奶牛数、FP奶牛数、团队大小// 读入FJ的N头奶牛得分for(inti=1;i<=n;i++)cin>>a[i];// 读入FP的M头奶牛得分for(inti=1;i<=m;i++)cin>>b[i];// 将FJ和FP的得分按降序排序// 排序后，a[i] >= a[i+1]，b[i] >= b[i+1]// 这样dp[i][j]中，a[i]和b[j]分别是当前考虑的最小元素sort(a+1,a+n+1,greater<int>());sort(b+1,b+m+1,greater<int>());// 初始化：选0对时，方案数为1（什么都不选也是一种方案）for(inti=0;i<=n;i++)for(intj=0;j<=m;j++)dp[i][j][0]=1;// 动态规划：枚举团队大小k，FJ前i头，FP前j头for(intk=1;k<=K;k++){for(inti=k;i<=n;i++)// i至少为k（FJ至少需要k头奶牛）{for(intj=k;j<=m;j++)// j至少为k（FP至少需要k头奶牛）{// 容斥原理：计算不考虑a[i]和b[j]时的方案数// dp[i-1][j][k]: 不选FJ的第i头奶牛// dp[i][j-1][k]: 不选FP的第j头奶牛// 两者相加后，dp[i-1][j-1][k]被重复计算了，需要减去dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k])%mod;dp[i][j][k]=(dp[i][j][k]+dp[i][j-1][k])%mod;dp[i][j][k]=(dp[i][j][k]-dp[i-1][j-1][k]+mod)%mod;// 如果FJ的第i头奶牛得分 > FP的第j头奶牛得分// 则可以将它们配成一对（作为第k对，且FJ获胜）// 加上从前面i-1和j-1中选k-1对的方案数if(a[i]>b[j]){dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k-1])%mod;}}}}// 输出答案：从FJ的n头和FP的m头中选K对，FJ获胜的方案数cout<<dp[n][m][K]<<endl;return0;}

【运行结果】

10 10 3 1 2 2 6 6 7 8 9 14 17 1 3 8 10 10 16 16 18 19 19 382