P4933 大师

知识点: 线性DP

原题面

题目要求:

给定一长度为 \(n\) 的序列 \(h\)。
求方向为从左到右的，等差数列个数。
\(n\le 10^3, h_{max} \le 2 \times 10^4\)

分析题意

显然的线性DP。
设 \(f_{i,j}\) 表示 最后一项是\(h_i\)，公差为 \(j\) 的等差数列的个数。

转移到 \(i\) 时，枚举前一个元素 \(k\)，公差 \(j\) 即为 \(h_i - h_k\)。
最后一项是 \(h_k\)，公差为 \(j\) 的等差数列的个数为 \(f_{k,j}\)。

如图，在其末尾添加一新元素，则显然有 \(f_{i,j} = f_{k,j} +1\)。
可能存在多个公差为 \(j\) 的位置 \(k\)，则有状态转移方程式：

需要枚举当前位置 和 前一个位置。
复杂度 \(O(n^2)\)，稳过。

公差为负数怎么办？

1. 为所有计算出的公差加上一个偏移量。
2. 正着反着做两次DP，并将两次的贡献求和。

一种空间换时间，一种时间换空间。
以下代码中使用了时间换空间的做法。

代码实现

//知识点:线性DP
/*
By:Luckyblock
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
#define ll long long
const int kMod = 998244353;
const int kMaxn = 1010;
const int kMaxh = 2e4 + 10;
//=============================================================
ll n, maxh, ans, h[kMaxn], f[kMaxn][kMaxh];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
//=============================================================
int main() {
  n = read();
  for (int i = 1; i <= n; ++ i) {
    h[i] = read(); 
    maxh = std :: max(h[i], maxh);
    for (int j = 1; j < i; ++ j) {
      int delta = h[i] - h[j];
      if (delta < 0) continue; //保证公差不为负数
      f[i][delta] += f[j][delta] + 1;
      f[i][delta] %= kMod;
    }
  }
  for (int i = 1; i <= n; ++ i) { //统计答案
    for (int j = 0; j <= maxh; ++ j) {
      ans = (ans + f[i][j]) % kMod;
    }
  }
  
  memset(f, 0, sizeof(f));
  for (int i = n; i >= 1; -- i) {
    for (int j = n; j > i; -- j) {
      int delta = h[i] - h[j];
      if (delta <= 0) continue; 
      //在从左向右的DP中计算了公差为0的数列，保证不重复，这里要保证公差 > 0
      f[i][delta] += f[j][delta] + 1;
      f[i][delta] %= kMod;
    }
  }
  for (int i = 1; i <= n; ++ i) {
    for (int j = 0; j <= maxh; ++ j) {
      ans = (ans + f[i][j]) % kMod;
    }
  }
  
  printf("%lld\n", (ans + n) % kMod); //加上长度为1的数列数。
  return 0;
}