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

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

382

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]);}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容