基础思路

• 状态设置

  • $F_{k,i}$ 表示公差为 $k$ 前 $i$ 个电塔的等差数列数。
  • 两个 $F$ 一个公差为 $k$，一个为 $-k$。

• 状态转移

  • 对于$F_{k, i}$，从所有在 $i$ 之前的的与第 $i$ 个电塔差为 $j$ 的 $F$ 方案加一转移而来。

    	for (int k = 0; k <= D; k++)
    	{
    		for (int i = 1; i <= n; i++)
    		{
    			for (int j = 1; j < i; j++)
    			{
    				if (h[i] - h[j] == k)
    				{
    					dp1[k][i] += dp1[k][j] + 1;
    					dp1[k][i] = dp1[k][i] mod;
    				}
    				if (h[i] - h[j] == -k)
    				{
    					dp2[k][i] += dp2[k][j] + 1;
    					dp2[k][i] = dp2[k][i] mod;
    				}
    			}
    			if(k != 0)
    				ans += dp1[k][i] + dp2[k][i], ans = ans mod;
    			else
    				ans += dp1[k][i], ans = ans mod;
    		}
    	}

然而只有65pts，毕竟接近 $\operatorname {O}(n^3)$ 的复杂度。

然后就在这个代码基础上用那个$O(nv)$的思路修改了，但是连样例都过不了。 求调orz

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

#define mod %998244353

using namespace std;

const int N = 1e3 + 10;
const int M = 1e4 + 10;

int n;
int h[N];
int dp1[M][N];//计算公差为+k 
int dp2[M][N];//计算公差为-k 
int G1[M];
int G2[M];
int ans = 0;
int D = 0, minH = 0x7fffffff, maxH = 0;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> h[i];
		minH = min(minH, h[i]);
		maxH = max(maxH, h[i]);
	}
	
	D = maxH - minH;
	
	for (int k = 0; k <= D; k++)
	{
		memset(G1, 0, sizeof(G1));
		memset(G2, 0, sizeof(G2));
		for (int i = 1; i <= n; i++)
		{
			if (h[i] - k >= 0)
				dp1[k][i] = G1[h[i] - k], G1[h[i]] += dp1[k][i] + 1;
			if (h[i] + k <= maxH && k)
				dp2[k][i] = G2[h[i] + k], G2[h[i]] += dp2[k][i] + 1;
			ans += dp1[k][i] + dp2[k][i];
		}
	}
	
	cout << ans + n;
	return 0;
}