思路
动态规划
看到题目就想到了最长上升子序列。
类比最长上升子序列，发现多了一个要求，可以多开一维。
设 \(f_{i, j}\) 表示以 \(i\) 为结尾，\(j\) 为公差的序列的长度（点的个数 $ - 1$），那么答案就为
\[\sum_{i = 1}^{n}\sum_{j = -\max(v)}^{\max(v)} f_{i,j} \]看上去是 \(O(nv)\) 的，但是两个数的公差是确定的，所以可以像最长上升子序列那样向前遍历，时间复杂度 \(O(n^2)\)。
代码
点击查看代码
/*
--------------------------------
| code by FRZ_29 |
| code time |
| 2024/08/10 |
| 11:27:38 |
| 星期六 |
--------------------------------
*/
#include <iostream>
#include <cstdio>
typedef long long LL;
using namespace std;
void RD() {}
template<typename T, typename... U> void RD(T &x, U&... arg) {
x = 0; int f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
x *= f; RD(arg...);
}
const int N = 1e3 + 5, M = 4e4 + 5, O = 20000;
const LL mod = 998244353;
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)
int n, h[N];
LL f[N][M], ans;
int main() {
RD(n);
LF(i, 1, n) RD(h[i]);
LF(i, 1, n) {
ans++;
RF(j, i - 1, 1) {
f[i][h[i] - h[j] + O] += f[j][h[i] - h[j] + O] + 1;
f[i][h[i] - h[j] + O] %= mod;
ans += f[j][h[i] - h[j] + O] + 1;
ans %= mod;
}
}
printf("%lld", ans);
return 0;
}
/* ps:FRZ弱爆了，没有想到O(nv)的做法 */
标签：ch,int,题解,RD,P4933,ans,序列,大师 From： https://www.cnblogs.com/FRZ29/p/18352129天上和掌上又何足计较，此岸和彼岸是一样的浪潮。