题解 P8100 【[USACO22JAN] Counting Haybales P】

Sol1 · 2022-02-04 20:32:37 · 题解

纪念一下 usaco Pt 首次过两个题，C 完全没往凸包上想（

首先这个操作就是 swap 一对差为 1 的。

手玩一下容易发现如果两个元素差 \geq 2 那么无论如何操作都不能交换它们的相对位置，相同的元素也可以假定不能交换。

那么只需要把不能 swap 的元素都从前往后连上边，就变成了一个 DAG 拓扑序计数问题。

但是一般的 DAG 拓扑序计数是不能做的，需要挖掘图的性质。差恰好为 1 和 n=5\times 10^3 提示奇偶性，发现奇数的拓扑序唯一，偶数一样，所以这个图实际上是两条拓扑序定死的链之间互相连边。

现在就可以 DP 了，设 f_{i,j} 为第一条链选了前 i 个点，第二条链选了前 j 个点，转移的时候看第一条链上的第 i+1 个点的入边是否全都在第一条链以及第二条链的前 j 个点里面，如果是的话转移到 f_{i+1,j}；另一条链的扩展同理。

于是做完了，时空复杂度 O(n^2)。

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

const long long mod = 1000000007;
long long dp[5005][5005];
int n, a[5005], pre[5005], pos[5005], idx[2][5005];

inline void Read() {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
}

inline void Solve() {
    int cnt[2] = {0};
    memset(pre, 0, sizeof(pre));
    memset(pos, 0, sizeof(pos));
    memset(idx, 0, sizeof(idx));
    for (int i = 1;i <= n;i++) {
        pos[i] = ++cnt[a[i] & 1];
        idx[a[i] & 1][cnt[a[i] & 1]] = i;
        for (int j = i;j >= 1;j--) {
            if (((a[i] ^ a[j]) & 1) && abs(a[i] - a[j]) != 1) {
                pre[i] = j;
                break;
            }
        }
    }
    for (int i = 0;i <= cnt[0];i++) {
        for (int j = 0;j <= cnt[1];j++) dp[i][j] = 0;
    }
    dp[0][0] = 1;
    for (int i = 0;i <= cnt[0];i++) {
        for (int j = 0;j <= cnt[1];j++) {
            if (pre[idx[0][i + 1]] <= idx[1][j]) dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
            if (pre[idx[1][j + 1]] <= idx[0][i]) dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod;
        }
    }
    cout << dp[cnt[0]][cnt[1]] << endl;
}

int main() {
    int t; cin >> t;
    while (t--) {
        Read();
        Solve();
    }
    return 0;
}