题目链接:https://www.luogu.com.cn/problem/P4933
设电塔高度数组为.
状态表示:
表示以第
个数结尾(必须包含)的公差为
的长度大于
的等差数列的数目。
由于的可能取值仅与
前面的数据相关,因此只需要枚举
就可以了。
状态计算:
含义:长度大于2的数列数目是以结尾的数列拼上
之后的数列的数目:
长度为2的数列:和
形成的数列,方案数目为1.
为了方便最后答案的累加,引入数组表示以
结尾的数列的数目,那么
,含义就是长度大于1的等差数列的数目加上只有
一项的方案数。计算
可以通过枚举
的可能取值去计算(
的最大范围:
),但是其实没有必要,因为不是这么大范围的
都有可能作为公差,所以简化为:
额外注意点:由于公差可正负,因此具体实现时可以将所有的d整体向右偏移一个合理大的常数(如20005),当然也可以将数组拓展一个维度,比如
代表长度大于1不减等差数列的数目,
代表长度大于1的递减等差数列的数目。最后说明:其实ans的计算也可以直接放在dp计算过程中,这样子sum数组就可以省去。
#include<bits/stdc++.h>
using namespace std;
const int N = 1001;
#define mod 998244353
int dp[N][40005], h[N], sum[N];
int n;
int main()
{
cin>>n;
for(int i = 1;i <= n; i++)cin>>h[i];
for(int i = 1;i <= n; i++)
{
sum[i] = 1;
for(int j = 1;j < i; j++)
{
int d = h[i] - h[j] + 20005;
dp[i][d] = ( dp[j][d] + 1 + dp[i][d] )%mod;
sum[i] = (sum[i] + dp[j][d] + 1)%mod;
}
}
int ans = 0;
for(int i = 1;i <= n; i++)
{
ans = ( ans + sum[i] )%mod;
}
cout<<ans;
return 0;
}