在下文，因为为了方便代码的理解同步，所以应用了百度翻译：
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;
}
注意取模，不然会出锅!
0 条评论