B. Yet Another Palindrome Problem

Link

Solution

最长回文子序列的变种，dp[i][j]表示s[i-j]中最长回文子序列长度，枚举长度和起始点，转移式见代码，最后判断最长长度是否大于等于3即可。

Code

int a[maxn], dp[maxn][maxn];

int main(int argc, char **argv) {
    int n, t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; i++)cin >> a[i];
        for (int i = 0; i < n; i++)dp[i][i] = 1;
        for (int len = 1; len < n; len++)
            for (int i = 0; i + len < n; i++)
                dp[i][i + len] = (a[i] == a[i + len]) ? dp[i + 1][i + len - 1] + 2 : max(dp[i + 1][i + len], dp[i][i + len - 1]);
        cout << ((dp[0][n - 1] >= 3) ? "YES" : "NO") << endl;
    }
    return 0;
}