P4933 大师

基础思路

• 状态设置

  • \(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)\) 的复杂度。

改进思路

我们可以把这个算法简化为，枚举一个公差 \(k\)，然后统计有多少个公差为 \(k\) 的等差数列。

枚举公差的时间复杂度是 \(\operatorname{O}(v)\)，观察数据范围可以猜测，统计的时间复杂度是，\(\operatorname{O}(n)\)，总复杂度是\(\operatorname{O}(n\times v)\)。

回顾 \(65\) 分的那个的 \(DP\)，用到这个统计上来，用 \(F_{k，i}\) 表示以 \(i\) 结尾的，公差为 \(k\) 的等差数列有多少个，转移的时候枚举一个小于 \(i\) 的 \(j\) ，然后当 \(h_j = h_i - k\) 时候从 \(F_{k, j}\) 转移到 \(F_{k, i}\)。

状态已经不可能再简化了，但是转移可以。

我们发现，转移相当于一个求和，对小于 \(i\) 的所有高度等于\(h_i - k\) 的位置的 \(DP\) 值求和。

我们可以维护一个数组 \(G\) 来记录这个和，这样转移就只有两行了。

总复杂度是\(\operatorname{O}(n\times v)\)

AC代码

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

#define mod %998244353
#define ll long long

using namespace std;

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

int n;
int h[N];
ll dp1[M][N];
ll dp2[M][N]; 
ll G1[M];
ll G2[M];
ll 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 >= minH)
				dp1[k][i] = G1[h[i] - k];
			if (h[i] + k <= maxH && k)
				dp2[k][i] = G2[h[i] + k];
			G1[h[i]] += dp1[k][i] mod + 1, G1[h[i]] mod;
			G2[h[i]] += dp2[k][i] mod + 1, G2[h[i]] mod;
			ans += (dp1[k][i] mod + dp2[k][i] mod ) mod, ans mod;
		}
	}
	cout << (ans + n) mod;
	return 0;
}

实现上还有有一定难度的

• 正确理解 \(G\) 数组的作用，无论是否能更新 \(dp1\) 都要更新 \(G\) 数组。
  • 因为该数组要记录在 \(i\) 之前的和，如果后面要用到，前面没更新就是错的。
• 取模。
  • ans 和所有有关动规的数组都要开 long long 而且每一步都要取模。