主要思路

主要还是需要注意设计状态。

我们称 \((-1, x)\) 为单对，称 \((-1, -1)\) 为双对。我们可以试着从大到小填数字，这样就可以避免取 \(\min\) 的问题了。考虑 \(dp[i][j][k]\) 为选到第 \(i\) 个数字，然后有 \(j\) 个待处理、\(k\) 个单对待处理。转移的话，可以试着进行讨论。如果这个数字是某个单对之一，那么一种方式是啥都不干，还有一种是尝试进行匹配，\(j -= 1\)。如果不是单对之一，那么要么匹配、要么晾着。

最后乘上一个双对个数的阶乘，使其有序。

代码

// AGC030F.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 330, mod = 1e9 + 7;

int n, ai[MAX_N << 1], dp[MAX_N << 1][MAX_N][MAX_N], both_nexist, single_exist, seq[MAX_N << 1], m;
bool vis[MAX_N << 1], pending[MAX_N << 1];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n << 1; i++)
        scanf("%d", &ai[i]);
    for (int i = 1; i <= n << 1; i += 2)
    {
        if (ai[i] > 0 && ai[i + 1] > 0)
            vis[ai[i]] = vis[ai[i + 1]] = true;
        else if (ai[i] < 0 && ai[i + 1] < 0)
            both_nexist++;
        else
            single_exist++, pending[max(ai[i], ai[i + 1])] = true;
    }
    for (int i = (n << 1); i >= 1; i--)
        if (!vis[i])
            seq[++m] = i;
    dp[0][0][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j <= both_nexist + single_exist; j++)
            for (int k = 0; k <= single_exist; k++)
            {
                if (!pending[seq[i]])
                {
                    dp[i][j + 1][k] = (0LL + dp[i][j + 1][k] + dp[i - 1][j][k]) % mod;
                    if (j > 0)
                        dp[i][j - 1][k] = (0LL + dp[i][j - 1][k] + dp[i - 1][j][k]) % mod;
                    if (k > 0)
                        dp[i][j][k - 1] = (0LL + dp[i][j][k - 1] + 1LL * k * dp[i - 1][j][k] % mod) % mod;
                }
                else
                {
                    dp[i][j][k + 1] = (0LL + dp[i][j][k + 1] + dp[i - 1][j][k]) % mod;
                    if (j > 0)
                        dp[i][j - 1][k] = (0LL + dp[i][j - 1][k] + dp[i - 1][j][k]) % mod;
                }
            }
    int ans = dp[m][0][0];
    for (int i = 1; i <= both_nexist; i++)
        ans = 1LL * ans * i % mod;
    printf("%d\n", ans);
    return 0;
}