10942번: 팰린드롬?

https://www.acmicpc.net/problem/10942


$O(n^2+m)$

모든 팰린드롬을 구할 때 나이브하게 짜면 n^2, manacher's 알고리즘을 쓰면 n 시간이 걸린다.
주어진 n이 작으므로 쿼리마다 n이 걸리는 방법으로 팰린드롬을 구하되, memorization을 이용해 시간을 단축한다.

#include<cstdio>
const int MAX_N = 2e3;
int n, m, a[MAX_N], pa[MAX_N][MAX_N], ck[MAX_N][MAX_N];
int f(int x, int y) {
    if (x > y) return 1;
    if (ck[x][y]) return pa[x][y];
    ck[x][y] = 1;
    return pa[x][y] = f(x + 1, y - 1)&(a[x] == a[y]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    scanf("%d", &m);
    for (int i = 0, x, y; i < m; i++) scanf("%d %d", &x, &y), printf("%d\n", f(x - 1, y - 1));
    return 0;
}