题解：CF2144E1 Looking at Towers (easy version)

E1 容易先处理出 $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 = L_j$ 若 $L_j$ 在之前已经被选择，则 $a_i$ 选不选均可，否则需要强制选，则有转移 $dp_{i,j} = 2dp_{i - 1,j} + dp_{i - 1,j - 1}$ 。
$a_i < L_j$ $a_i$ 的选择不会对 $L^\prime$ 造成影响，则有转移 $dp_{i,j} = 2dp_{i - 1,j}$ 。
$a_i > L_j$ 不能选择 $a_i$ ，否则会破坏 $L = L^\prime$ ，则有转移 $dp_{i,j} = dp_{i - 1,j}$ 。

当统计答案时，需要小心重复计算的情况。因此当

a_i

为全局最大值时，强制让

dp1

去选择这个最大值，然后强制

dp_2

不选这个最大值，则对答案的贡献为

(dp1_{i,cntL} - dp1_{i - 1,cntL}) \times dp2_{i + 1,cntR - 1}

。

时间复杂度为

O(n^2)

，代码如下：

CPP

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);
}

题解：CF2144E1 Looking at Towers (easy version)

文章操作

相关推荐

评论

题解：CF2144E1 Looking at Towers (easy version)