题解 P2098 【[USACO16DEC]Team Building团队建设】

大头 · 2017-02-14 20:23:42 · 题解

为啥我是一血（233）

dp水题。

快排预处理。

f[i][j][k]表示匹配上了i头牛，FJ选择的是他的前j头牛，FP选择的是前K头牛的方案数。

状态转移见代码。

时间效率O（nmk）

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#define mo 1000000009
using namespace std;
int a[1005],b[1005],f[12][1005][1005],n,m,p;
int main(){
    scanf("%d%d%d",&n,&m,&p);
    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+n+1);
    sort(b+1,b+m+1);
    for (int i=0;i<=n;i++)
        for (int j=0;j<=m;j++) f[0][i][j]=1;
    for (int i=1;i<=p;i++){
        for (int j=1;j<=n;j++)
            for (int k=1;k<=m;k++)
                if (a[j]>b[k]) f[i][j][k]=f[i-1][j-1][k-1];
        for (int j=1;j<=n;j++)
            for (int k=1;k<=m;k++) f[i][j][k]=(f[i][j][k]+f[i][j][k-1])%mo;
        for (int j=1;j<=n;j++)
            for (int k=1;k<=m;k++) f[i][j][k]=(f[i][j][k]+f[i][j-1][k])%mo;
        }
    printf("%d",f[p][n][m]);
}