핵심 아이디어

<aside> 💡

$dp_i = i$까지 짝수 팰린드롬으로 나눴을 때 짝수 팰린드롬의 최대 개수

짝수 팰린드롬으로 나눌 수 없다면 $-2$이다.

투포인터로 짝수 팰린드롬인지 확인 하고 짝수 팰린드롬으로 나눌 수 있다면 $dp_i$를 1개 늘린다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long int ll;

int n;
int a[5'001];

int dp[5'001];

int go(int i)
{
    int &ret = dp[i];
    if(ret != -1) return ret;
    
    for(int j = i-2; j>=0; j-=2){
        int prv = go(j);
        if(prv == -2) continue;

        bool flag = true;
        int lidx = j+1;
        int ridx = i;
        while(lidx<ridx){
            if(a[lidx] != a[ridx]){
                flag = false;
                break;
            }
            lidx++;
            ridx--;
        }

        if(flag){
            ret = max(ret, prv+1);
        }
    }

    if(ret == -1) return ret = -2;
    else return ret;
}

signed main()
{
    FASTIO;
    cin >> n;
    for(int i = 1; i<=n; i++){
        cin >> a[i];
    }

    memset(dp, -1, sizeof(int)*(n+1));
    dp[0] = 0;

    int ans = go(n);
    cout << (ans!=-2?ans:-1);
    
    return 0;
}