P4933 大师
本题链接：P4933 大师
本博客给出本题截图：
AC代码
代码解释：
f[i][j]代表的是在以第 i 项结尾，公差为 j 的所有等差数列的数量，在这里我们可以知道，如果我们 j 按照从 1 ~ M 来暴力枚举，显然会 TLE 思考后会发现，我们如果只去枚举 h[i] - h[j] 即可，因为可能会有负数：递减的等差数列，故可能会有 h[i] - h[j] < 0，这里我们把数组开成两倍之后用 h[i] - h[j] + M / 2 即可
这里提一下状态转移方程：
f[i][t] = (f[i][t] + f[j][t] + 1) % mol;
这里为什么要 + 1，可以理解成 在所有的以 j 结尾的数列多加一个 i ，再加上单独由 j 和 i 组成的这么一组数列
注意 dp 过程中我们不讨论只有一个电塔的情况，故我们的 res 初始化为 n
代码：
#include <cstdio> #include <algorithm> using namespace std; #include <cstdio> #include <algorithm> using namespace std; const int N = 1010, mol = 998244353, M = 40010; int h[N]; int f[N][M]; int n; int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]); int res = n; for (int i = 1; i <= n; i ++ ) { for (int j = i - 1; j; j -- ) { auto t = h[i] - h[j] + M / 2; f[i][t] = (f[i][t] + f[j][t] + 1) % mol; res = (res + f[j][t] + 1) % mol; } } printf("%d\n", res); return 0; }
