关于昨天晚上ABC D题的求调
  • 板块题目总版
  • 楼主georgeyu123
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/7/30 08:37
  • 上次更新2023/11/3 06:58:24
查看原帖
关于昨天晚上ABC D题的求调
731709
georgeyu123楼主2023/7/30 08:37

本人代码test019挂了,其他都过了。

显示:

AC * 23

WA * 1

代码:

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

# define ll long long
# define N 3005
# define mod 998244353

int n;
ll dp[N][N];
// dp[i][j] 表示到第 i 位有 j 个未被配对的左括号的总方案数量
string Tmp;
char s[N];

signed main() {
  cin >> Tmp;
  int n = Tmp.size();
  if (n == 0) {
    cout << 1 << endl;
  }
  for (int i = 0; i < n; ++i) {
    s[i + 1] = Tmp[i];
  }
  if (n & 1) { 
    cout << 0 << endl;
    return 0;
  } 
  if (s[1] == ')') {
    cout << 0 << endl; 
  }
  memset (dp, 0, sizeof dp);
  dp[1][1] = 1;
  for (int i = 2; i <= n; ++i) { 
    if (s[i] == '(') {
      dp[i][0] = 0;
      for (int j = 0; j <= i; ++j) 
        dp[i][j + 1] = dp[i - 1][j];
    } else if (s[i] == ')') { 
      for (int j = 1; j <= i; ++j) { 
        dp[i][j - 1] = dp[i - 1][j]; 
      }
    } else {
      for (int j = 0; j <= i; ++j) {
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
        dp[i][j] %= mod;
      }
    }
  }
  cout << dp[n][0] % mod << endl;
  return 0;
}
2023/7/30 08:37
加载中...