当前位置：首页 > news >正文

打卡信奥刷题（2545）用C++实现信奥 P2098 [USACO16DEC] Team Building P

news 2026/6/30 14:51:06

P2098 [USACO16DEC] Team Building P

题目描述

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

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

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

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

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

输入格式

输入的第一行包含NNN、MMM和KKK。KKK的值不会超过NNN或MMM。

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

C++实现

#include<cstdio>#include<cstdlib>#include<iostream>#include<cmath>#include<algorithm>#include<cstring>#definemo1000000009usingnamespacestd;inta[1005],b[1005],f[12][1005][1005],n,m,p;intmain(){scanf("%d%d%d",&n,&m,&p);for(inti=1;i<=n;i++)scanf("%d",&a[i]);for(inti=1;i<=m;i++)scanf("%d",&b[i]);sort(a+1,a+n+1);sort(b+1,b+m+1);for(inti=0;i<=n;i++)for(intj=0;j<=m;j++)f[0][i][j]=1;for(inti=1;i<=p;i++){for(intj=1;j<=n;j++)for(intk=1;k<=m;k++)if(a[j]>b[k])f[i][j][k]=f[i-1][j-1][k-1];for(intj=1;j<=n;j++)for(intk=1;k<=m;k++)f[i][j][k]=(f[i][j][k]+f[i][j][k-1])%mo;for(intj=1;j<=n;j++)for(intk=1;k<=m;k++)f[i][j][k]=(f[i][j][k]+f[i][j-1][k])%mo;}printf("%d",f[p][n][m]);}