在下文,因为为了方便代码的理解同步,所以应用了百度翻译:

summit: 顶点

valley: 流域; 山谷,溪谷,峡谷,谷地,深谷;


这显然是道 $DP$ 题 (废话)

可以知道题目要求的合法山脉其实是一个波动数列。

很容易的可以想到,设 $summit[i][j]$ 表示长度为 $j$ 的波动数列,此波动数列的第一个数为 $i$,且在题目中,$i$ 为山峰,这样状态下的方案总数。

同样的,我们同时设 $valley[i][j]$ 表示长度为 $j$ 的波动数列,此波动数列的第一个数为 $i$,且在题目中,$i$ 为山谷,这样状态下的方案总数。

那么答案是多少呢?由于数列中的每一个元素都可以做第一个元素,且都有可能做” 山峰” 或者是” 山脉”,所以我们的答案应该是:

$\sum_{i=1}^{n} summit[i][n]+valley[i][n]$

现在来考虑怎么转移。

以 $summit$ 的转移为例子,假设现在需要转移 $summit[i][n]$.

那么这个波动数列的第二项肯定严格小于 $i$ ,而第三项又严格大于第二项,所以如果不看第一项的话,这个数列就变成了由第二项起头,并且第二项是” 山谷”,设第二项的数为 $j$ ,那么其方案数可以用 $valley[j][n-1]$ 来表示。

由于第二项可以是数列中严格小于 $i$ 的任何数,因此我们可以列出转移式:

$summit[i][n] = \sum_{k=1}^{i-1} valley[k][n-1]$

因为题目说了是严格小于,所以可以这样子统计,亲,放心哦!这样子不会出锅!

同样的,$valley[i][j]$ 也是这样转移:

$valley[i][n] = \sum_{k=i}^{n-1} summit[k][n-1]$

我们现在可以很轻易的打出正解了,但是想象一下,我们有那么大的空间吗?$2 \times 4200 \times 4200$?貌似很紧诶 (虽然我是踩线没有 $MLE$)

那就使用滚动数组!

还有,这样子统计,复杂度将会是 $O(n^3)$ !怎么优化呢?

前缀和就好了呀!

然后…… 然后就没有然后了……

Code:

#include<bits/stdc++.h>
#define ll long long
#define RI register int 
#define A printf("A")
using namespace std;
const int N=4205;
template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}
int summit[N][2],valley[N][2],ans,sum,p;
int main(){
    scanf("%d%d",&sum,&p);
    summit[2][0]=1,valley[1][0]=1,valley[2][0]=1;
    for(int n=3;n<=sum;++n)
       for(int i=1;i<=n;++i){
           int sum_val,sum_sum;
           sum_val=(summit[n-1][(n-1)&1]-summit[i-1][(n-1)&1]+p)%p;
           valley[i][n&1]=(valley[i-1][n&1]+sum_val)%p;
           sum_sum=valley[i-1][(n-1)&1]%p;
           summit[i][n&1]=(summit[i-1][n&1]+sum_sum)%p;
       }
    ans=(valley[sum][sum&1]+summit[sum][sum&1])%p;
    printf("%d\n",ans);
    return 0;   
}

注意取模,不然会出锅!

分类: 文章

Qiuly

QAQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注