AT4541 Permutation 题解

youyou2007 · 2021-09-25 13:33:09 · 题解

Description

给定一个数字 n，表示有一个长度为 n 的序列，又给定一个长度为 n-1 字符串 s，里面仅包含 < 和 >。

当 1 ≤ i ≤ n - 1 时，s[i] 表示数列中第 i 个元素与第 i + 1 个元素的关系。

求满足字符串 s 关系的 1 ~ n 的排列一共有多少种，方案数对 10^9+7 取模。

constraints

Solution 1 TLE

考虑DP。

设 f[i][j] 表示已经考虑了前 i 个位置，且第 i 位上，填的数字是第 j 小的总方案数。

不难想到初始状态即用 1 填了 1 位，即 f[1][1] = 1 。

由于每一位必由前一个位置转移过来，所以可以分两种情况：

• 这个位置是 <，根据状态定义，前一位要比这个小，即 f[i][j] += f[i - 1][k] (k < j)；

• 这个位置是 >，前一位要比这个大，但是，在 i-1 时的第 j 小，由于现在加入了一个第 j 小的数，将上次的第 j 小变成了现在的 j+1 小，所以需要加上 f[i - 1][k]。即 f[i][j] += f[i - 1][k] (j ≤ k < i)；

由于这个复杂度是 O(n^3)，因此还是会超时。

Solution 2 AC

上面的算法复杂度较高，考虑优化，但状态已经优化到了二维，考虑优化转移。

发现最内层循环时，由于要统计上一个数的所有可能转移的位置，耗费了较多时间。

由于可能转移的位置肯定都是一个连续的段，且是它们之和，可以前缀和优化。设 sum[j] 表示从 f[i-1][1] 到 f[i-1][j] 的数值之和，转移时直接计算即可。

时间复杂度为 O(n^2)。

核心代码：

    f[1][1] = 1;//初始值
    for(int i = 2; i <= n; i++)
    {
        memset(sum, 0, sizeof sum);//每一次sum要清空
        for(int j = 1; j <= i - 1; j++)
        {
            sum[j] = sum[j - 1] + f[i - 1][j];//sum记录前缀和
        }
        for(int j = 1; j <= i; j++)
        {
            if(s[i] == '<')//处理小于号
            {
                f[i][j] = (f[i][j] + sum[j - 1] - sum[0]) % MOD;
            }
            else//处理大于号
            {
                f[i][j] = (f[i][j] + sum[i - 1] - sum[j - 1]) % MOD;
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)//最后答案是f[n][i]的总和
    {
        ans = (ans + f[n][i]) % MOD;
    }

Code

Solution 1 代码

Solution 2 有注释代码