코드
시간 : 312 ms
메모리 : 17728 KB
#include<bits/stdc++.h>
using namespace std;
int dp[2005][2005];
int arr[2005];
int main(){
int n,M;
memset(arr,-1,sizeof(arr));
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
scanf("%d",&M);
for(int i=0;i<n/2;i++){
dp[i][i] = 1;
if(arr[i] == arr[i+1]){
dp[i][i+1] = 1;
}
for(int j=0;j<=i;j++){
if(arr[i-j] == arr[i+j] && dp[i-j+1][i+j-1] == 1){
dp[i-j][i+j] = 1;
}
if(arr[i-j] == arr[i+j+1] && dp[i-j+1][i+j] == 1){
dp[i-j][i+j+1] = 1;
}
}
}
for(int i=n/2;i<n;i++){
dp[i][i] = 1;
if(arr[i] == arr[i+1]){
dp[i][i+1] = 1;
}
for(int j=0;j<=n-i;j++){
if(arr[i-j] == arr[i+j] && dp[i-j+1][i+j-1] == 1){
dp[i-j][i+j] = 1;
}
if(arr[i-j] == arr[i+j+1] && dp[i-j+1][i+j] == 1){
dp[i-j][i+j+1] = 1;
}
}
}
for(int q=0;q<M;q++){
int s,e;
scanf("%d %d",&s,&e);
printf("%d\n",dp[s-1][e-1]);
}
}
C++
복사