题解 | GCPC总决赛（状态压缩dp）

定义dp[s][k][p]为在s状态下 DarknessCatcher得k分，yxlxszx得q分的情况数。对于状态s：我们选择固定b数组，重新排列a数组来达到全部匹配的情况，其中s的二进制为1的位表示选择a[i]进行匹配。状态转移方程：当前选择a[j]，若a[j]==b[i]：dp[s][p][k]+=dp[s^(1<<j)][p][k]；若a[j]<b[i]：dp[s][p][k]+=dp[s^(1<<j)][p][k-1]；若a[j]>b[i]：dp[s][p][k]+=dp[s^(1<<j)][p-1][k]；最后统计不同比分组合的胜负情况

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll = long long;
const ll N = 5e5 + 9;
typedef pair<ll, ll> pi;
vector<ll> ne[N];
bool st[N];
void solve()
{
	ll n;
	cin>>n;
	vector<ll> a(n+10),b(n+10);
    for(ll i=0;i<n;i++)
    cin>>a[i];
    for(ll i=1;i<=n;i++)
    cin>>b[i];
	vector<vector<vector<ll>>> dp(1<<n,vector<vector<ll>>(n+10,vector<ll>(n+10)));
    dp[0][0][0]=1;
	for(ll s=1;s<1<<n;s++)
	{
		ll i=0;
        ll m=s;
        while(m)
        {
            i+=m&1;
            m>>=1;
        }
        for(ll j=0;j<n;j++)
        {
            if(!((s>>j)&1))
            continue;
            for(ll k=0;k<=n;k++)
            {
                for(ll p=0;p<=n;p++)
                {
                    // if(k==p&&k==0)
                    // continue;
                    if(a[j]<b[i]&&p>0)
                    dp[s][k][p]+=dp[s^(1<<j)][k][p-1];
                    if(a[j]>b[i]&&k>0)
                    dp[s][k][p]+=dp[s^(1<<j)][k-1][p];
                    if(a[j]==b[i])
                    dp[s][k][p]+=dp[s^(1<<j)][k][p];
                }
            }
        }
	}
    // cout<<dp[3][0][1]<<endl;
    ll ans0=0,ans1=0,ans2=0;
    for(ll i=0;i<=n;i++)
    for(ll j=0;j<=n;j++)
    {
        if(i==j)
        ans1+=dp[(1<<n)-1][i][j];
        else if(i>j)
        ans0+=dp[(1<<n)-1][i][j];
        else
        ans2+=dp[(1<<n)-1][i][j] ;
    }
    cout<<ans0<<" "<<ans2<<" "<<ans1<<endl;
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}