【bzoj4742: [Usaco2016 Dec]Team Building】dp

4742: [Usaco2016 Dec]Team Building

Time Limit: 10 Sec  
Memory Limit: 128 MB
Submit: 168  
Solved: 98
[ Submit][ Status][ Discuss]

Description

Every year, Farmer John brings his NN cows to compete for "best in show"at the state fair. His arch
-rival, Farmer Paul, brings his MM cows to compete as well (1≤N≤1000,1≤M≤1000).Each of the N+MN+
M cows at the event receive an individual integer score. However, the final competition this year wi
ll be determined based on teams of KK cows (1≤K≤10), as follows: Farmer John and Farmer Paul both 
select teams of KK of their respective cows to compete. The cows on these two teams are then paired 
off: the highest-scoring cow on FJ's team is paired with the highest-scoring cow on FP's team, the s
econd-highest-scoring cow on FJ's team is paired with the second-highest-scoring cow on FP's team, a
nd so on. FJ wins if in each of these pairs, his cow has the higher score.Please help FJ count the n
umber of different ways he and FP can choose their teams such that FJ will win the contest. That is,
 each distinct pair (set of KK cows for FJ, set of KK cows for FP) where FJ wins should be counted. 
Print your answer modulo 1,000,000,009.
매년 농부 존은 그의 N마리 소를 데리고 집회에 가서'넌 최고야'경기에 참가한다. 그의 상대인 농부 폴도 M마리 소를 데리고 경기에 참가했다.
(1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000).소마다 모두 자신의 점수가 있다.두 사람은 K마리 소를 선택해 팀을 구성한다(1≤K≤10), 두 팀
소는 점수의 크기에 따라 순서를 정한 후에 하나하나 짝을 지었고 존은 바울당을 물리쳤으며, 단지 한 쌍의 소에게만 존의 소 점수가 바울보다 높았다.도와 주세요.
존은 존이 바울을 물리치는 방안수mod 100000009를 계산했다.두 가지 방안이 다르고, 단지 존이나 바울이 선택한 소의 집합이 다른 것과 같다
방안이 다르다.

Input

The first line of input contains N, M, and K. The value of K will be no larger than N or M.
The next line contains the N scores of FJ's cows.
The final line contains the M scores of FP's cows.

Output

Print the number of ways FJ and FP can pick teams such that FJ wins, modulo 1,000,000,009.

Sample Input

10 10 31 2 2 6 6 7 8 9 14 171 3 8 10 10 16 16 18 19 19

Sample Output

382
존의 소는 a[i] 바울의 소는 b[i]
f[i][j][k]=존의 전 i마리 소와 바울의 전 j마리 소가 각각 k마리를 골라 비교할 때 존이 바울을 물리치는 방안 수
상태 전환 방정식을 사용할 수 있습니다.
f[i][j][k]=f[i-1][j][k]+f[i][j-1][k]-f[i-1][j-1][k]+f[i-1][j-1][k-1]*(a[i]>b[j]);
f[i-1][j][k]+f[i][j-1][k]-f[i-1][j-1][k]는 a[i]가 필수이거나 b[j]가 필수인 것을 가정한 것이기 때문에 a[i]>b[j]라면 전 i-1, j-1마리의 소가 k-1쌍을 비교하고 마지막에 a[i]와 b[j]를 취하면 모두 k쌍이 승리하는 방안 수를 구성할 수 있다.
(내가 정렬을 하나 추가했으니 사용하지 않을 것이다)

#include
#include
#include
#define MOD 1000000009
#define N 1050
using namespace std;
int n,m,k,a[N],b[N];
long long f[N][N][11];
bool cmp(int a,int b){
	return a>b;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+m,cmp);
	for(int i=0;i<=n;i++)for(int j=0;j<=m;j++) f[i][j][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int p=1;p<=min(k,min(i,j));p++)
				f[i][j][p]=(MOD+f[i-1][j][p]+f[i][j-1][p]-f[i-1][j-1][p]+(a[i]>b[j])*f[i-1][j-1][p-1])%MOD;
	printf("%d
",f[n][m][k]);
}