BZOJ 4742 [Usaco2016 Dec]Team Building

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=4742

题意:略。

思路:把两组牛都混在一起从大到小排序,相同分数的时候后者排前面,那么问题转化为,从排序后的序列中选择kAB,使得任意一个前缀中A的个数不比B的个数少。考虑定义dp[i][j][k]表示考虑前i张牌,选了jA,kB的方案数,保证(j>=k),直接转移即可,时间复杂度O((n+m)(k^2+log(n+m)))

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2000+10;
const int P=1e9+9;
struct Node{
    int val,tp;
    bool operator<(const Node&rhs)const{
        if (val==rhs.val) return tp>rhs.tp;
        return val>rhs.val;
    }
}p[N];
int n,m,k,x,i,j,l,cnt,dp[N][20][20];
inline void up(int&a,int b){a+=b;if(a>=P)a-=P;}
int main(){
    read(n),read(m),read(k);
    for (i=1;i<=n;++i){
        read(x);
        p[++cnt].val=x;
        p[cnt].tp=1;
    }
    for (i=1;i<=m;++i){
        read(x);
        p[++cnt].val=x;
        p[cnt].tp=2;
    }
    sort(p+1,p+1+cnt);
    for (dp[0][0][0]=1,i=1;i<=n+m;++i){
        for (j=0;j<=k;++j)for(l=0;l<=j;++l){
            if (p[i].tp==1 && j-1>=l) up(dp[i][j][l],dp[i-1][j-1][l]);
            if (p[i].tp==2 && l>=1) up(dp[i][j][l],dp[i-1][j][l-1]);
            up(dp[i][j][l],dp[i-1][j][l]);
        }
    }
    printf("%d\n",dp[n+m][k][k]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注