动态规划题目随解

持续更新。

CF258D Little Elephant and Broken Sorting

Link\((^*2600)\)

给定排列 \(p\)，有 \(m\) 次操作，每次操作给定 \(x,y\)，等概率选择是否交换。求 \(\sum\limits_{i=1}^{n}\sum\limits_{j=i}^{n}P(p_i>p_j)\)。

\(n,m\leq 10^3\)。

考虑直接设 \(f_{l,r}\) 表示 \(p_l>p_r\) 的概率。初始化很好初始化，我们考虑直接对操作进行转移。

假如我们要交换 \(p_l\) 和 \(p_r\)，那么此时其本身 \(f_{l,r}=f_{r,l}=0.5\)。对于 \(\forall x\neq l,r\)，考虑不交换和交换之后的改变。

可以分以下情况讨论：

1. \(f_{x,l}=\dfrac{f_{x,l}+f_{x,r}}{2}\)；
2. \(f_{r,x}=\dfrac{f_{r,x}+f_{l,x}}{2}\)；
3. \(f_{l,x}=\dfrac{f_{l,x}+f_{r,x}}{2}\)；
4. \(f_{x,r}=\dfrac{f_{x,r}+f_{x,l}}{2}\)。

容易发现 \(1\) 和 \(4\)、\(2\) 和 \(3\) 的转移是相同的，可以一起处理。最后扫一遍即可，\(O(n^2)\)。

Code(Tap)

for(int i = 1; i <= m; i++)
{
    int l, r;
    read(l, r);
    f[l][r] = f[r][l] = 0.5;
    for(int x = 1; x <= n; x++)
    {
        if(x == l || x == r) continue;
        f[x][l] = f[x][r] = ((f[x][l] + f[x][r]) / 2.00);
        f[r][x] = f[l][x] = ((f[r][x] + f[l][x]) / 2.00);
    }
}

CF1185G2 Playlist for Polycarp

Link\((^*2600)\)

给定 \(n\) 首歌，每首歌有时间 \(t_i\) 与流派 \(g_i\)。需要从中排列若干首歌，使得时间恰好为 \(T\)，且相邻流派不同。

\(1\leq n\leq 50,1\leq T\leq 2500,1\leq t_i\leq 50,1\leq g_i\leq 3\)。

不妨设 \(f_{i,j,k,1/2/3}\) 表示三种流派分别选了 \(i,j,k\) 首，最后一首为 \(1/2/3\) 的方案数。这个显然是很好转移的，时间复杂度 \(O(n^3)\)。由于我们要求的是排列，因此还要乘一个 \(i!j!k!\)。

然后我们在考虑相邻流派不同，时间恰好为 \(T\) 的方程。这个有点类似于背包，但是直接背包时间复杂度是 \(O(n^3T)\) 的，不能接受。

这里有一个比较巧妙的方法：将背包拆分成两个背包之后再分别求解。即我们记 \(g_{i,t}\) 为选择 \(1\) 的背包，\(h_{j,k,t}\) 为选择 \(2,3\) 的背包。这样时间复杂度分别为 \(O(nT),O(n^2T)\)。最后我们只需要枚举 \(g\) 的 \(t\)，\(h\) 的 \(t\) 可以由 \(T-t\) 得出。

最后我们将答案乘在一起即可。

Code(Tap)

f[1][0][0][1] = f[0][1][0][2] = f[0][0][1][3] = 1;
for(int i = 0; i <= n1; i++)
    for(int j = 0; j <= n2; j++)
        for(int k = 0; k <= n3; k++)
            for(int v = 1; v <= 3; v++)
            {
                if(f[i][j][k][v] == 0) continue;
                if(v != 1) f[i + 1][j][k][1] += f[i][j][k][v], f[i + 1][j][k][1] %= mod;
                if(v != 2) f[i][j + 1][k][2] += f[i][j][k][v], f[i][j + 1][k][2] %= mod;
                if(v != 3) f[i][j][k + 1][3] += f[i][j][k][v], f[i][j][k + 1][3] %= mod;
            }
g[0][0] = h[0][0][0] = 1;
for(int i = 0; i < n1; i++)
    for(int j = i; j >= 0; j--)
        for(int k = T - a[1][i]; k >= 0; k--)
            g[j + 1][k + a[1][i]] += g[j][k], g[j + 1][k + a[1][i]] %= mod;
for(int i = 0; i < n2; i++)
    for(int j = i; j >= 0; j--)
        for(int k = T - a[2][i]; k >= 0; k--)
            h[j + 1][0][k + a[2][i]] += h[j][0][k], h[j + 1][0][k + a[2][i]] %= mod;
for(int i = 0; i < n3; i++)
    for(int j = n2; j >= 0; j--)
        for(int k = i; k >= 0; k--)
            for(int v = T - a[3][i]; v >= 0; v--)
                h[j][k + 1][v + a[3][i]] += h[j][k][v], h[j][k + 1][v + a[3][i]] %= mod;
int ans = 0;
for(int i = 0; i <= n1; i++)
    for(int j = 0; j <= n2; j++)
        for(int k = 0; k <= n3; k++)
            for(int t = 0; t <= T; t++)
                if(g[i][T - t])
                    ans += ((f[i][j][k][1] + f[i][j][k][2]) % mod + f[i][j][k][3]) % mod * fct[i] % mod * fct[j] % mod * fct[k] % mod * h[j][k][t] % mod * g[i][T - t] % mod, ans %= mod;

CF1699E Three Days Grace

link\((^*2600)\)

给定 \(n\) 个元素的可重集 \(S\)，值域为 \([1,m]\)，你可以进行若干次操作：选择 \(A_i\in S\)，将其拆分成 \(p\cdot q=A_i\)，删除 \(A_i\) 并加入 \(p,q\)。需要最小化极差。

\(1\leq n\leq 10^6, 1\leq m\leq 5\cdot 10^6\)。

想象一个竖直的数轴，考虑将一个点拆分的过程实际相当于将比较高的点变换到比较低的位置。

这给我们一个启示：答案一定在一个区间 \([l,r]\) 内，进一步我们可以找出类似于双指针的方法：固定 \(l\)，并从大到小维护 \(r\)。

于是我们不妨设 \(f_{l,i}\) 表示区间下界在 \(l\)，当前枚举到点 \(i\)，此时的最小最大值。

考虑转移到 \(j\)，若 \(j\) 不能被拆分出来，那么 \(f_{l,i}=f_{l+1,i}\)；如果 \(j\) 可以被拆分出来，那么我们把这个拆出去，\(f_{l,i}=\min\{f_{l,\frac{j}{i}}\,f_{l,i}\}\)。由于不一定只拆出来一个 \(i\)，所以这里我们可以用一些多重背包的思想。

但是这样是不能接受的。考虑怎么优化：首先可以压掉第一维，然后第二维从 \(i\times i\) 开始每次 \(+i\)，是调和级数级别的。

然后我们考虑在 \(i\) 不变的情况下，随着 \(l\) 下降，\(f\) 是单调递减的。因此我们可以对 \(f\) 数组开桶，用指针向下扫到第一个存在值的位置。

这样的时间复杂度是 \(O(m\log m)\) 的。

Code(Tap)

read(n, m);
memset(a, 0, (m + 1) * 8);
memset(t, 0, (m + 1) * 8);
int lim = 1e9 + 7, ans = 1e9 + 7;
for(int i = 1; i <= n; i++)
{
    int x = read();
    lim = min(lim, x);
    a[x] = t[x] = 1;
}
for(int i = 1; i <= m; i++) f[i] = i;
int pt = m;
for(int i = m; i; i--)
{
    if(i * i <= m)
    {
        for(int j = i * i; j <= m; j += i)
        {
            t[f[j]] -= a[j];
            f[j] = min(f[j], f[j / i]);
            t[f[j]] += a[j]; 
        }
    }
    while(!t[pt]) pt--;
    if(i <= lim) ans = min(ans, pt - i);
}
printf("%lld\n", ans);