区间DP求调

#include <bits/stdc++.h>
using namespace std;

#define int __int128

inline int Read() {
  int x = 0,f = 1;
  char c = getchar();
  for(;c < '0' || c > '9';c = getchar()) f ^= (c == '-');
  for(;c >= '0' && c <= '9';c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
  return f ? x : -x;
}

void Print(int x,int flag = 1) {
  if(!x) return;
  Print(x / 10,0);
  putchar(x % 10 + '0');
  if(flag) puts("");
}

const int _ = 505;

int n;
string s;
int a[_],dp[_][_],vis[_][_],flag[_][_];

int Count(int x,int y) {
  if(x > 3 || (y != 0 && y < 4)) return 0; 
  if(x == 0 && y == 0) return 3;
  if(x == 0 || y == 0) return 1;
  if(x == y - 3) return 1;
  return 0;
}

int DP(int x,int y) {
  if(x > y || dp[x][y]) return dp[x][y];
  for(int i = x + 1;i <= y;i += 2) {
	dp[x][y] += Count(a[x],a[i]) * DP(x + 1,i - 1) * (i + 1 > y ? 1 : DP(i + 1,y));
	if(dp[x][y] > 100000) dp[x][y] %= 100000,flag[x][y] = 1;
  }
  return dp[x][y];
}

signed main() {
  n = Read();
  cin >> s,s = ' ' + s;
  map<char,int> mp;
  mp['('] = 1,mp['['] = 2,mp['{'] = 3,mp[')'] = 4,mp[']'] = 5,mp['}'] = 6;
  for(int i = 1;i <= n;i++) {
  	a[i] = mp[s[i]];
  	dp[i][i - 1] = 1;
  }
  dp[n + 1][n] = 1;
  DP(1,n);
  if(flag[1][n]) {
  	if(dp[1][n] < 10000) putchar('0');
  	if(dp[1][n] < 1000) putchar('0');
  	if(dp[1][n] < 100) putchar('0');
  	if(dp[1][n] < 10) putchar('0');
	Print(dp[1][n]);
  } else {
  	Print(dp[1][n]);
  }
  return 0;
}