题解 | #奇思妙想波奇酱#

奇思妙想波奇酱

观察发现 b 很小，所以直接搜，但是还发现有点重复，记 f[x] 为 以 x 为端点后半段能否构造，显然可以记忆化，直接秒了。

#include<bits/stdc++.h>
// #define int long long
using namespace std;
using i64 = long long;
void solve() {
    int n; cin >> n;
    vector<int> b(n + 1);
    vector<int> f(n + 1, -1);
    for(int i = 1; i <= n; ++i) cin >> b[i];
    function<bool(int, i64, int, bool)> dfs = [&](int x, i64 sum, int i, bool fl) -> bool {
        // cout << x << " " << sum << " " << i << " " << fl << endl;
        // if(x > n) return 0;
        if(sum < 0 || sum > 1e8) return 0;
        if(x == n) {
            return fl ? sum == b[x] : sum == 0;
        }
        bool res = 0;
        if(fl) {
            res = dfs(x + 1, sum + i * i * b[x], i + 1, 1);
            if(sum == b[x]) {
                if(~f[x + 1]) res = f[x + 1];
                else res |= f[x + 1] = dfs(x + 1, 0, 1, 1) || dfs(x + 1, b[x + 1], 1, 0);
            }
        }
        else {
            if(sum == 0) {
                if(~f[x + 1]) res = f[x + 1];
                else res = f[x + 1] = dfs(x + 1, 0, 1, 1) || dfs(x + 1, b[x + 1], 1, 0);
            }
            else res = dfs(x + 1, sum - i * i * b[x + 1], i + 1, 0);
        }
        return res;
    };
    cout << (dfs(0, 0, 0, 0) ? "Yes" : "No") << endl;
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}