RT

这是 90pts TLE #10 代码：

#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int M = 1e9 + 7;
int n, sum, tx, ty, T[12], S[12], K[12];
map<unsigned int, int> mp; 
int mod(int &a) {
    while (a >= M) a -= M;
}
inline int dfs(const int &i, const int &j, const int &x, const int &y) {
    if (x > tx || y > ty) return 0;
    if (i == n + 1) return 1;
    else if (j > n) {
        if (S[i] != T[i]) return 0;
        for (register int k = i + 1; k <= n; k++) K[k] = T[k] - S[k];
        sort(K + i + 1, K + n + 1);
        unsigned int H = 0;
        for (register int k = i + 1; k <= n; k++) H = H * 29ll + K[k] + 1;
        if (mp.count(H)) return mp[H];
        else {
            mp[H] = dfs(i + 1, i + 2, x, y);
            return mp[H];
        }
    } 
    if (S[i] > T[i] || S[i] + (n - j + 1) * 3ll < T[i]) return 0;
    int cnt = 0;
    // i，j 平
    S[i]++, S[j]++;
    cnt += dfs(i, j + 1, x, y + 1);
    S[i]--, S[j]--;
    // i 胜
    S[i] += 3;
    cnt += dfs(i, j + 1, x + 1, y);
    S[i] -= 3;
    // j 胜
    S[j] += 3;
    cnt += dfs(i, j + 1, x + 1, y);
    S[j] -= 3;
    return mod(cnt);
}
bool cmp(const int &a, const int &b) { return a > b; }
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (register int i = 1; i <= n; i++) {
        cin >> T[i];
        sum += T[i];
    }
    sort(T + 1, T + n + 1, cmp); 
    tx = sum - n * (n - 1), ty = n * (n - 1) * 3 / 2 - sum;
    cout << dfs(1, 2, 0, 0);
    return 0;   
}

这是 AC 代码：

#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int M = 1e9 + 7;
int n, sum, tx, ty, T[12], S[12], K[12];
map<unsigned int, int> mp; 
int mod(int &a) {
    while (a >= M) a -= M;
}
inline int dfs(const int &i, const int &j, const int &x, const int &y) {
    if (x > tx || y > ty) return 0;
    if (i == n + 1) return 1;
    else if (j > n) {
        if (S[i] != T[i]) return 0;
        for (register int k = i + 1; k <= n; k++) K[k] = T[k] - S[k];
        sort(K + i + 1, K + n + 1);
        unsigned int H = 0;
        for (register int k = i + 1; k <= n; k++) H = H * 29ll + K[k] + 1;
        if (mp.count(H)) return mp[H];
        else {
            mp[H] = dfs(i + 1, i + 2, x, y);
            return mp[H];
        }
    } 
    if (S[i] > T[i] || S[i] + (n - j + 1) * 3ll < T[i]) return 0;
    int cnt = 0;
    // i 胜
    if (S[i] + 3 <= T[i] && x + 1 <= tx) {
        S[i] += 3;
        cnt += dfs(i, j + 1, x + 1, y);
        S[i] -= 3;
    }
    // i，j 平
    if (S[i] + 1 <= T[i] && S[j] + 1 <= T[j] && y + 1 <= ty) {
        S[i]++, S[j]++;
        cnt += dfs(i, j + 1, x, y + 1);
        S[i]--, S[j]--;
    }
    // j 胜
    if (S[j] + 3 <= T[j] && x + 1 <= tx) {
        S[j] += 3;
        cnt += dfs(i, j + 1, x + 1, y);
        S[j] -= 3;
    }
    return mod(cnt);
}
bool cmp(const int &a, const int &b) { return a > b; }
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (register int i = 1; i <= n; i++) {
        cin >> T[i];
        sum += T[i];
    }
    sort(T + 1, T + n + 1, cmp); 
    tx = sum - n * (n - 1), ty = n * (n - 1) * 3 / 2 - sum;
    cout << dfs(1, 2, 0, 0);
    return 0;   
}

为什么我在进入递归前判断是否可行就不会 TLE？

难道是因为判断的常数？