【动态规划、dp】P4933 大师

题目描述

ljt12138 首先建了 $n$ 个特斯拉电磁塔，这些电塔排成一排，从左到右依次标号为 $1$ 到 $n$，第 $i$ 个电塔的高度为 $h[i]$。

建筑大师需要从中选出一些电塔，然后这些电塔就会缩到地下去。这时候，如果留在地上的电塔的高度，从左向右构成了一个等差数列，那么这个选择方案就会被认为是美观的。

建筑大师需要求出，一共有多少种美观的选择方案，答案模 $998244353$。

注意，如果地上只留了一个或者两个电塔，那么这种方案也是美观的。地上没有电塔的方案被认为是不美观的。

同时也要注意，等差数列的公差也可以为负数。

说明/提示

设 $v$ 为最高的电塔高度。

对于前 $30\%$ 的数据，$n \le 20 $。

对于前 $60\%$ 的数据，$n\le 100$，$v\le 2\times 10^3$。

对于另外 $20\%$ 的数据，所有电塔的高度构成一个等差数列。

对于 $100\%$ 的数据，$n\le 10^3$，$v\le 2\times 10^4$。

思路

记 $d{p}_{i,j}$ 表示以第 $i$ 个数结尾，公差是 $j$ 的等差数列个数（不包括只有 $1$ 个数的情况），那么显然的转移：

$$d{p}_{i,j}=\sum _{k=1}^{i-1}(d{p}_{k,j}+1),(h_i-h_k=j)$$

其中加一是为了增加只有 $(h_i,h_k)$ 两个数字的等差数列情况。最后答案加上只有一个数的等差数列个数 $n$ 即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,h[1005],dp[1005][40005]; 
const int P = 998244353;
int ans = 0;
signed main() {scanf("%lld",&n);for(int i = 1;i <= n;i++) scanf("%lld",&h[i]);for(int i = 1;i <= n;i++) {for(int j = 1;j < i;j++) {int t = h[i] - h[j];t += 20000;if(dp[j][t]) dp[i][t] += dp[j][t];dp[i][t]++;dp[i][t] %= P;}for(int j = 0;j <= 40000;j++) {ans += dp[i][j],ans %= P;}}printf("%lld\n",(ans + n) % P);return 0;
}