洛谷 P2467 题解

admin 2021-07-17 AM 136℃ 0条

题目链接

分析

感觉这个思路比较正常,常数也不大。

首先这是个明显的 DP 题。

显然至少应该设 $dp_{i,j}$ 为前 $i$ 个数的排列中,以 $j$ 结尾的方法数。

发现不好转移,因为无法判断最后一个数和倒数第二个数之间的大小关系。

扩充一下 DP 状态:设 $dp_{i,j,0/1}$ 为前 $i$ 个数的排列中,以 $j$ 结尾的方法,最后一个数比前一个数小/大的方法数。

转移方程显然:

$$dp_{i,j,0}=\sum_{k=j}^{i-1}dp_{i-1,k,1}$$

$$dp_{i,j,1}=\sum_{k=1}^{j-1}dp_{i-1,k,0}$$

(考虑最后一个数插入的位置即可)

这样转移是 $O(n^3)$ 的,可能可以 70 分。

考虑优化一下。显然 $dp_{i,j,0/1}$ 转移只和 $dp_{i-1,k,0/1}$ 中连续的一段有关。可以滚动数组 & 前缀和优化。

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

解决

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 4205;
int dp[N][2], sum[N][2], n, p;

int main()
{
    cin >> n >> p;
    dp[1][0] = dp[2][1] = 1;
    for (int i = 3; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            sum[j][0] = (sum[j - 1][0] + dp[j][0]) % p;
            sum[j][1] = (sum[j - 1][1] + dp[j][1]) % p;
        }
        for (int j = 1; j <= i; j++)
        {
            dp[j][0] = (sum[i - 1][1] - sum[j - 1][1] + p) % p;
            dp[j][1] = sum[j - 1][0];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = (ans + (dp[i][0] + dp[i][1]) % p) % p;
    cout << ans << endl;
    return 0;
}
标签: none

非特殊说明,本博所有文章均为博主原创。

评论啦~