题解 P2159 【[SHOI2009]舞会】

Rui_R · 2020-11-24 18:48:56 · 题解

不错的DP题。但是需要高精就很恶心……

原题

本文更像是对Thyer大佬题解的解释。因为我们的做法高度相似，但是Thyer大佬的题解不太详细，于是就有了此文。

观察数据范围，n \le 200，初步判断为 n^3 的DP。但是注意到，没有模数。数数题没有模数……好家伙，需要高精，而高精巨大的常数就意味着不可能是 n^3 的。

首先想到将男女按身高排序，得到一些优秀的性质。具体见后文。

然后，考虑固定男人的位置不变，接着把女人一个一个与男人配对。

那么，令 dp[i][j] 表示考虑前 i 个位置（也就是男人）与前 i 个女人匹配，其中有 j 组满足女伴高于男伴的方案数。

答案为 \sum_{i=0}^k dp[n][i]

尝试转移：

如果当前女人不高于男人：

1：当前女人不会使 j 增加：

此时，当前女人可以放到任意满足男人身高大于等于当前女人身高的位置上，同时将该位置上的女人放到当前位置上，形成新的方案。

记满足这样要求的位置有 Alpha 个。O(n) 扫一遍就可以得到 Alpha。

或者，可以将当前女人放到任意原来就是女伴更高的位置。由于女人身高已经过排序，交换后“原来就是女伴更高的位置”仍然是女伴更高，而当前位置也仍然是男人不矮于女人。

满足这样要求的位置显然有 j 个。

同时， j 与 Alpha 不可能有重叠部分。因为 Alpha 的部分满足男人不矮于女人。

综上，对于 dp[i][j] ，能使 j 增加的位置有 j+Alpha 个。

2：当前女人会使 j 增加：

这个简单，用总位置数 i 减掉上面的就好。

得到“当前女人不高于男人”的状态转移方程：

那么如果当前女人高于男人：

1：当前女人不会使 j 增加：

此时她无论放到哪里都会形成一组“女伴更高”的组合。（因为男人已经按身高排序）那么不会使 j 增加就等于将一个原来女伴更高的组合中的女伴放到当前男人的位置，同时她不高于当前男人。

也就是“原来女伴更高的部分”减去高于当前男人的部分。

那么记之前的女伴中，高于当前男人的女人有 Alpha 个，（显然她们都形成了“女伴更高”的组合），满足当前要求的位置就有 j-Alpha 个。

2：当前女人会使 j 增加：

用总位置数 i 减掉上面的就好。

得到“当前女人高于男人”的状态转移方程：

由于 dp[i][] 只会跟 dp[i-1][] 有关，可以再用滚动数组优化空间。

如果对细节感到好奇，或者想白嫖高精的，见代码。

#include <bits/stdc++.h>
using namespace std;

const int maxn=205;

int n,k;int M[maxn],W[maxn];

struct Int{
    #define max_size (501)
    int val[max_size];int len;const int base=10;//压位的部分就先不管了
    Int(int _val=0){len=1;for(int i=0;i<max_size;i++) val[i]=0;*this=_val;}
    Int(const char s[max_size]){init(s);}
    Int(char s[max_size]){init(s);}
    int& operator[](const int id){return val[id];}
    void operator=(int _val){
        for(int i=0;i<=len;i++) val[i]=0;
        len=0;while(_val) val[++len]=_val%10,_val/=10;
    }
    void operator=(Int pos){
        *this=0;len=pos.len;
        for(int i=1;i<=len;i++) val[i]=pos.val[i];
    }
    void carry_bit(){
        for(int i=1;i<=len;i++){
            if(val[i]>9){
                val[i+1]+=val[i]/10;
                val[i]%=10;
                if(i==len) len++;
            }
        }
    }
    void eat_zero(){
        for(;!val[len]&&len>1;len--);
        if(!len) len=0,val[len]=0;
    }
    Int operator+(int _val){
        Int now=*this;now[1]+=_val;
        now.carry_bit();return now;
    }
    Int operator+(Int _val){
        Int now=*this;now.len=max(now.len,_val.len);
        for(int i=1;i<=_val.len;i++) now[i]+=_val[i];
        now.carry_bit();return now;
    }
    Int operator*(int _val){
        Int now=*this;
        for(int i=1;i<=len;i++) now[i]*=_val;
        now.carry_bit();return now;
    }
    Int operator*(Int _val){
        Int now;now.len=len+_val.len-1;
        for(int i=1;i<=now.len;i++){
            for(int j=1;j<=_val.len;j++){
                now[i+j-1]+=val[i]*_val[j];
            }
        }
        now.eat_zero();
        now.carry_bit();return now;
    }
    Int operator/(int _val){
        Int now=*this;
        for(int i=len;i>=1;i--){
            if(i) now[i-1]+=base*(now[i]%_val);
            now[i]/=_val;
        }
        now.eat_zero();return now;
    }
    bool operator<(Int _val)const{
        if(len!=_val.len) return len<_val.len;
        for(int i=len;i>=1;i--){
            if(val[i]!=_val[i]) return val[i]<_val[i];
        }
        return 0;
    }
    bool operator==(Int _val)const{
        if(len!=_val.len) return 0;
        for(int i=len;i>=1;i--){
            if(val[i]!=_val[i]) return 0;
        }
        return 1;
    }
    bool operator>(Int _val)const{
        if(len!=_val.len) return len>_val.len;
        for(int i=len;i>=1;i--){
            if(val[i]!=_val[i]) return val[i]>_val[i];
        }
        return 0;
    }
    bool operator<=(Int _val)const{return !(*this>_val);}
    bool operator>=(Int _val)const{return !(*this<_val);}
    void init(const char s[max_size]){
        len=0;int begin=0;
        for(int i=1;s[i]>='0'&&s[i]<='9';i++){
            if(!begin&&s[i]==48) continue;
            if(!begin){begin=i;}len++;
        }
        if(!begin){len=0,val[1]=0;return;}
        for(int i=1;i<=len;i++){
            val[i]=s[len-i+begin]-48;
        }
    }
    void operator=(const char s[max_size]){this->init(s);}
    void print(){
        eat_zero();if(!len) putchar(48);
        else for(int i=len;i>=1;i--) putchar(val[i]+48);
        putchar('\n');
    }
};

//这个高精板子并不太靠谱……并且不支持负数
//如果你还是想用的话，那我只能说：
//El Psy Congroo.

Int dp[2][maxn];

int main(){
    // freopen("P2159_1.in","r",stdin);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&M[i]);
    for(int i=1;i<=n;i++) scanf("%d",&W[i]);
    std::sort(M+1,M+n+1),std::sort(W+1,W+n+1);
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        int Alpha=0,Sg=i&1;
        for(int j=0;j<=i;j++) dp[Sg][j]=0;
        if(M[i]>=W[i]){
            for(int j=1;j<=i;j++) if(M[j]>=W[i]) Alpha++;
            for(int j=0;j<=i;j++)
            dp[Sg][j]=dp[!Sg][j]*(j+Alpha);
            for(int j=1;j<=i-Alpha;j++)
            dp[Sg][j]=(dp[Sg][j]+dp[!Sg][j-1]*(i-Alpha-(j-1)));
        }
        else{
            for(int j=1;j< i;j++) if(W[j]>M[i])  Alpha++;//注意不要取等号，因为这里Alpha统计的是在i之前的
            for(int j=1;j<=i;j++)
            dp[Sg][j]=dp[Sg][j]+dp[!Sg][j-1]*(i-((j-1)-Alpha));
            for(int j=Alpha;j<=i;j++)
            dp[Sg][j]=dp[Sg][j]+dp[!Sg][j]*(j-Alpha);
        }
    }
    Int answer=0;
    for(int i=0;i<=k;i++) answer=answer+dp[n&1][i];
    answer.print();
    return 0;
}