1001 - Link with Bracket Sequence II

给定一串括号序列，序列中的一些括号丢失了，这些位置用 $0$ 表示，其他的位置表示已经确定的括号，如果大于 $0$，则代表左括号，小于 $0$ 代表右括号。数字的绝对值表示这种括号的类型(不止一种类型的括号)

已知括号的种类为 $m$ 种，试问有多少种方案将这个序列填充为合法括号序列

考虑区间 dp。
$$f(i, j):=这个区间内的全部合法括号序列方案数 \\ g(i, j):=这个区间i,j这两个括号匹配时的序列方案数$$
转移时先考虑 $g$，枚举 $i, j$ 上填的括号，如果匹配，就把 $g(i + 1, j - 1)$ 乘上有多少种匹配，然后就转移到了 $f(i, j)$。

再从 $f$ 转回 $g$。
$$g(i, j) = g(i,j)+g(i,j-1) \times f(i,j) + g(i,j+1) \times f(i+2,j)+…+g(i,j-1)\times f(j-1,j)$$

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    vector f(n + 1, vector<Mint>(n + 1));
    vector g(n + 1, vector<Mint>(n + 1));
    for (int i = 1; i <= n; i++) {
      g[i][i - 1] = 1;
    }
    for (int len = 2; len <= n; len += 2) {
      for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1;
        assert(l >= 1 && l <= n);
        assert(r >= 1 && r <= n);
        if (a[l] >= 0 && a[r] <= 0) {
          int valid = 0;
          if (a[l] == 0 && a[r] == 0){
            valid = m;
          }
          else if (a[l] == 0 || a[r] == 0 || (a[l] + a[r] == 0)){
            valid = 1;
          }
          f[l][r] = g[l + 1][r - 1] * valid;
        }
        for (int k = l; k <= r - 1; k += 2){
          g[l][r] += g[l][k - 1] * f[k][r];
        }
      }
    }
    cout << g[1][n] << '\n';
  }
  return 0;
}

1007 - Climb Stairs

给定 $n$ 层楼层，每一层都有一个敌人，血量为 $a_i$ ，你的初始攻击力为 $a_0$ ，每次你选择向上跳 $1,2,3,…,k$ 层，或者向下跳一层，但是不能跳到之前走过的楼层，跳到的楼层里的敌人血量必须不大于你的攻击力，每跳到一个楼层，你将击败楼层里的敌人，并且使得攻击力增加 $a_i$ 。问能否消灭所有的敌人。

首先可以发现，我们不能连续跳跃两次，如果从 $x$ 跳到了 $y$，下一步需要干的是往下跳，消灭所有 $x, y$ 之间的敌人。这个过程是 $O(n)$ 的，可以优化。

考虑从第一层跳到第三层。
$$a_0 >= a_3 \\ a_0 + a_3 >= a_2 \\ a_0 + a_3 + a_2 >= a_1$$
等价于
$$a_0 >= a_3 \\ a_0 >= a_2-a_3 \\ a_0 >= a_1-a_2-a_3 \\ $$
维护差分即可。

于是就可以贪心的跳了，每次跳到能消灭那层敌人且能消灭起点到终点之间的敌人的位置。

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, a0, k;
    cin >> n >> a0 >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    long long pref = 0, between = 0;
    int jump = 0;
    for (int i = 0; i < n; i++) {
      if (jump == k) {
        jump = 1e9;
        break;
      }
      if (a0 >= a[i] && a0 + a[i] >= between) {
        a0 += a[i] + pref;
        jump = pref = between = 0;
      } else {
        jump++;
        pref += a[i];
        between = max(between - a[i], 1ll * a[i]);
      }
    }
    cout << (jump > 0 ? "NO" : "YES") << '\n';
  }
  return 0;
}