BZOJ 5124: [Lydsy1712月赛]波浪序列

同2017多校4I题
k维比较只要重载一下运算符即可
\(dp[i][j][0/1]\) 表示第一个数组的前 \(i\) 个，第二个数组以第 \(j\) 个结尾，且当前上升状态为 \(0/1\)
转移方程为
\(dp[i][j][k]+=dp[i-1][j][k]\)
当 \(a[i]=b[j]\) 时
\(dp[i][j][0]+=\sum\limits_{k<j\wedge b[k]<b[j]}dp[i-1][k][1]\)
\(dp[i][j][1]+=\sum\limits_{k<j\wedge b[j]<b[k]}dp[i-1][k][0]\)
后面可以用前缀和优化
上面的转移只有在 \(a[i]=b[j]\) 时才能转移，先枚举 \(i\) 的话，\(b[j]\) 就确定了
\(dp[i][j][0]+=\sum\limits_{k<j\wedge b[k]<a[i]}dp[i-1][k][1]\)
\(dp[i][j][1]+=\sum\limits_{k<j\wedge a[i]<b[k]}dp[i-1][k][0]\)
用两个变量记录一下前缀和即可。

#include <bits/stdc++.h>

const int MOD = 998244353;
const int N = 2200;

inline void M(int &x) {
  if (x >= MOD)
    x -= MOD;
}

int dp[N][N][2], n, m, k;

struct P {
  int arr[7];
  void read() {
    for (int i = 1; i <= k; i++) 
      scanf("%d", arr + i);
  }
  bool operator < (const P &p) const {
    int cnt = 0;
    for (int i = 1; i <= k; i++) 
      cnt += arr[i] < p.arr[i];
    return cnt == k;
  }
  bool operator == (const P &p) const {
    int cnt = 0;
    for (int i = 1; i <= k; i++) 
      cnt += arr[i] == p.arr[i];
    return cnt == k;
  }
} a[N], b[N];

int main() {
  scanf("%d", &k);
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    a[i].read();
  scanf("%d", &m);
  for (int i = 1; i <= m; i++)
    b[i].read();
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      dp[i][j][0] = dp[i][j][1] = 0;
  for (int i = 0; i <= n + 10; i++)
    dp[i][0][0] = 1;
  for (int i = 1; i <= n; i++) {
    int sum0 = 1, sum1 = 0;
    for (int j = 1; j <= m; j++) {
      M(dp[i][j][0] += dp[i - 1][j][0]);
      M(dp[i][j][1] += dp[i - 1][j][1]);
      if (a[i] == b[j]) {
        M(dp[i][j][0] += sum1);
        M(dp[i][j][1] += sum0);
      }
      if (b[j] < a[i])
        M(sum1 += dp[i - 1][j][1]);
      if (a[i] < b[j])
        M(sum0 += dp[i - 1][j][0]);
    }
  }
  int ans = 0;
  for (int i = 1; i <= m; i++)
    M(ans += dp[n][i][0]), M(ans += dp[n][i][1]);
  printf("%d\n", ans);
  return 0;
}

BZOJ 5124: [Lydsy1712月赛]波浪序列

原文：https://www.cnblogs.com/Mrzdtz220/p/12261689.html