Search
Duplicate

팰린드롬 ?

생성일
2021/03/20 18:19
번호
10942
유형
dp

코드

시간 : 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++
복사