[Leaf] [P4933] 大师

p4933-大师---洛谷">P4933 大师 - 洛谷

1. 题面梗概

中译中：给出一个非负数列，求它有多少个等差子序列。

$n \leq 1000, a_{i} \leq 20000$，有负数

2. 逻辑推导

虽然形式上是计数问题，但这还是一个 “子序列提取” 问题，只不过这次转移的条件不再只局限于相邻两数。

2.1 状态1

为了保证下一个加入的数能是等差数列，得知道再上一个数或者公差。

我们给 DP 加上公差这一维度：用 $f[i][d]$ 来表示以第 $i$ 个数结尾，公差为 $d$ 的子序列的个数。

那么就可以只考虑相邻事件，得到一个有点丑的转移方程：

$$f[i][d] = \sum_{j < i \text{且} a_{i} = a_{j} + d}( f[j][d] + 1 )$$

复杂度为 $O( N^2 V )$，观察发现，很多情况下 $i$ 结尾并没有很多种公差可供选择，没必要把所有的 $d$ 都遍历一遍，换个写法如下：

$$f[i][a_{i} - a_{j}] = \sum_{j < i}( f[j][a_{i} - a_{j}] + 1)$$

很明显，这样需要枚举的两个维度都不超过 $n$，所以总复杂度为 $O( n^2 )$。

2.2 状态2

另一个思路是枚举 $d$，然后对每个 $d$ 做一次动态规划。

定义：$f[v]$ 为当前公差下，以 $v$ 结尾的等差数列总数。

如果 $a[i] - d \in [0, V]$ 则 $cnt = f[ a[i] - d ] +1$。

更新状态：$f[ a[i] ] = f[ a[i] ] + cnt$

这种写法的时间复杂度也是 $O( nv )$，但是空间复杂度是 $O( n + v )$

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e3 + 5;
const int maxv = 2e4 + 5;
const int mod = 998244353;

int f[maxn][maxv << 1];
int h[maxn];
int n;

int main( )
{
    cin >> n;
    for( int i = 1; i <= n; ++ i ) cin >> h[i];

    ll ans = 0;
    for( int i = 1; i <= n; ++ i )
    {
        for( int j = 1; j < i; ++ j )
        {
            int d = h[i] - h[j] + maxv;
            f[i][d] = ( f[i][d] + f[j][d] + 1 ) % mod;
            ans = ( ans + (ll)f[j][d] + 1 ) % mod;
        }
    }

    cout << ( ans + n ) % mod << '\n';
    return 0;
}

4. 复盘

• 复杂度分析：时间 $O(N \cdot V)$。

• 碎碎念：计数类的子序列提取问题。

• 关联笔记：线性DP