没用滚动数组瞎写居然没有被卡空间!!!!
这题在省选题里还是算比较简单的
蒟蒻第一次写题解
题意分析
首先我们根据题意
·这N段山脉每段都可以修建瞭望台或酒馆的其中之一
就是要求长度为n的上下滚动的数组数量,例如
(n=5) 1 4 2 5 3
就是一组。
方法分析
冥思苦想两分钟好像并没有此类公式...偷懒失败~
很容易想到用dp,我们用f ( i , j )表示当 n = i 时,以j为开头的方案数量
我们不妨设第一个j是山峰(由对称性最后ans*2即可)
先上转移方程(递推公式)
f(i,j)=f(i,j-1)+f(i-1,i-j+1)
接下来解释为什么
考察j与j-1的位置关系
-
若j与j-1不相邻
互换j与j-1,仍然得到的是一族合法的序列,且以j-1开头。具体为什么...自己写几个就会发现规律~
所以 f(i,j)+=f(i,j-1) -
若j与j-1相邻
这个情况复杂一些 其实只需要计算以j-1为山谷的排列数量
山谷怎么办呢?
想到把后面的数字全部反转,即 l --> n+1-l 不难发现得到的仍是合法序列。
并且讨厌的山谷,变成了山峰!
所以 f(i,j)+=(i-1,i-j+1)
我们就得到了转移方程~~~
代码欣赏
惊现邪教活动代码!
//僕らのラブライブ!サンシャイン!!
//P2467
#include<bits/stdc++.h>
using namespace std;
const int maxn=4205;
int f[maxn][maxn];
int n,mod,ans;
int main(){
cin>>n>>mod;
f[1][1]=1;
f[2][2]=1; //初始条件
for(int i=3;i<=n;i++){
for(int j=2;j<=i;j++){
f[i][j]=(f[i][j-1]+f[i-1][i-j+1])%mod;
}
}
for(int j=2;j<=n;j++) {
ans+=f[n][j];
ans%=mod;
}
cout<<ans*2%mod; //别忘记模了
}