题解：CF2144E1 Looking at Towers (easy version)

· · 题解

容易先处理出 L(a) 和 R(a)，设元素个数分别为 cntL,cntR。

接下来考虑 DP。设 dp1_{i,j} 表示前 i 个数选了 L 中的前 j 个数的方案；dp2_{i,j} 表示后 i 个数选了 R 中的前 j 个数的方案。两者方程相似，故下面只对 dp1 进行讲解。

考虑转移，对于当前的数 a_i，以及 L 的前 j 个数已经被选择，可以分为以下三种情况：

当统计答案时，需要小心重复计算的情况。因此当 a_i 为全局最大值时，强制让 dp1 去选择这个最大值，然后强制 dp_2 不选这个最大值，则对答案的贡献为 (dp1_{i,cntL} - dp1_{i - 1,cntL}) \times dp2_{i + 1,cntR - 1}。

时间复杂度为 O(n^2)，代码如下：

void solve ()
{
    int n = read (),mx = 0;
    vector <int> a (n + 1),L (n + 1),R (n + 1);
    vector <vector <int>> dp1 (n + 1,vector <int> (n + 1)),dp2 (n + 2,vector <int> (n + 2));
    for (int i = 1;i <= n;++i) a[i] = read ();
    int cntL = 0,cntR = 0;
    for (int i = 1;i <= n;++i)
        if (mx < a[i]) L[++cntL] = a[i],mx = a[i];
    mx = 0;
    for (int i = n;i;--i)
        if (mx < a[i]) R[++cntR] = a[i],mx = a[i];
    dp1[0][0] = dp2[n + 1][0] = 1;
    for (int i = 1;i <= n;++i)
    {
        for (int j = cntL;~j;--j)
        {
            if (L[j] == a[i]) dp1[i][j] = (dp1[i - 1][j] * 2 % MOD + dp1[i - 1][j - 1]) % MOD;
            else if (L[j] > a[i]) dp1[i][j] = dp1[i - 1][j] * 2 % MOD;
            else dp1[i][j] = dp1[i - 1][j];
        }
    }
    for (int i = n;i >= 1;--i)
    {
        for (int j = cntR;~j;--j)
        {
            if (R[j] == a[i]) dp2[i][j] = (dp2[i + 1][j] * 2 % MOD + dp2[i + 1][j - 1]) % MOD;
            else if (R[j] > a[i]) dp2[i][j] = dp2[i + 1][j] * 2 % MOD;
            else dp2[i][j] = dp2[i + 1][j];
        }
    }
    ll ans = 0;
    for (int i = 1;i <= n;++i) 
    {
        if (a[i] != mx) continue;
        ans = (ans + 1ll * ((dp1[i][cntL] - dp1[i - 1][cntL] + MOD) % MOD) * dp2[i + 1][cntR - 1] % MOD) % MOD;
    }
    printf ("%lld\n",ans);
}