dp

part1.正常地前缀和优化写法

最朴素的版本:

\(dp[i][j][k]\)表示考虑到1-i的情况,最后一个数为j,倒数第二个数为k的方案数。(注意:这里的j,k并不是实际的数值,而表示在前i个数中的大小排名

直接大力转移就好了。

复杂度:\(O(n^4)\)

优化境界1:

容易发现,我们用关心倒数第二个数与最后一个数的相对大小就行了。

于是状态就变成了\(dp[i][j][0/1]\)表示考虑到1-i的情况,最后一个数为j,倒数第二个数比最后一个数小/大的方案数。

然后就可以70分dp了。

转移方程:
\[dp[i][j][0]=\sum _{k=1}^{k\le j-1}dp[i-1][k][1]\]

\[dp[i][j][1]=\sum_{k=j}^{k\le i-1}dp[i-1][k][0]\]

复杂度:\(O(n^3)\)

代码:

dp[1][1][0] = dp[1][1][1] = 1;
for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= i; j++) {//枚举最后一个数是多少
        for (int k = 1; k < i; k++) {//i在1-i-1中肯定是最大的,因此其可以视作i-1(这里好好理解一下)
            if (k < j)
                dp[i][j][0] = (dp[i][j][0] + dp[i - 1][k][1]) % MOD;
            else
                dp[i][j][1] = (dp[i][j][1] + dp[i - 1][k][0]) % MOD;
        }
    }
}

优化境界2:

很显然维护个前缀和以及后缀和就好了。

就不必多说了。

复杂度:\(O(n^2)\)

代码:

#include<bits/stdc++.h>
#define MAXN 4210
using namespace std;
int dp[MAXN][MAXN][2],n,MOD,ans,sum[MAXN][MAXN][2];
int main() {
    scanf("%d %d",&n,&MOD);
    dp[1][1][0]=dp[1][1][1]=1;
    for(int i=2; i<=n; i++) {
        for(int j=1; j<=i-1; j++)sum[i-1][j][0]=(sum[i-1][j-1][0]+dp[i-1][j][1])%MOD;
        for(int j=i-1; j>=1; j--)sum[i-1][j][1]=(sum[i-1][j+1][1]+dp[i-1][j][0])%MOD;
        for(int j=1; j<=i; j++) {
            dp[i][j][0]=sum[i-1][j-1][0];
            dp[i][j][1]=sum[i-1][j][1];
        }
    }
    for(int i=1; i<=n; i++)ans=(0LL+ans+dp[n][i][0]+dp[n][i][1])%MOD;
    cout<<ans;//注意,当n=1时要特判,但实际上数据并没有这个点
    return 0;
}

part2.一种用组合数的写法

前置芝士1:

根据这个性质,我们可以得到一下结论:

1.除了n=1以外,长度为n的合法序列一定有偶数个

2.最后一位为山峰和最后一位为山谷的数量一定是一样多的。

3.第一位为山峰和第一位为山谷的数量一定是一样多的。

\(dp[i]\)表示长度为i的方案数。

对于一个i,我们枚举其插入的位置为j,那么其左边有j-1段山脉,右边有i-1-j段山脉。

这样,左边那j-1段需满足最后一个为山谷,右边i-1-j段需满足第一个为山谷。

根据性质结论,容易得知左边有\(dp[j-1]/2\)种是合法的,右边有\(dp[i-1-j]/2\)种是合法的。同时在i-1个数选j-1个放在左边又有\(C_{i-1}^{j-1}\)种方法。

于是就有
\[dp[i]=\sum_{j=1}^{j\le i} (dp[j-1]/2)\cdot(dp[i-1-j]/2)\cdot C_{i-1}^{j-1}\]

但是这道题让我们模P,而且P还不是固定的,也就是说:若P为奇数,还要用exgcd求2的模逆元QAQ。(P不一定是质数)

因此,我们可以定义\(dp[i]\)表示长度为i,开头为山峰的合法序列数量(反正最后×2就是答案了)。

复杂度:\(O(n^2)\)

part3.又一种写法

前置知识1:(part2有提到)

前置知识2:

状态定义:\(dp[i][j]\)表示考虑到1-i,最后一个数为j且j做为山峰的合法方案数。

状态转移:

\[dp[i][j]=dp[i][j-1]+dp[i-1][i-j+1]\]
这样就好了?

我来解释一下:

首先,若j和j-1不相邻,根据前置知识2,我们拿j和j-1换一下,又成了合法序列,所以这部分答案为\(dp[i][j-1]\)

那么,接着我们就需要统计j和j-1相邻的方案数。由于j和j-1相邻,且j作为山峰,那么最后两个肯定是j-1,j。

于是这个问题就变成了:在长度为i-1的序列中,求以j-1作为山谷的方案数

根据前置知识2,j-1作为山谷与(i-1)-(j-1)作为山峰肯定是一一对应的。所以这部分答案就为\(dp[i-1][(i-1)-(j-1)+1]\)

最后再把答案乘以2就好了。

01-02 20:38