题解 P2467 【[SDOI2010]地精部落】
残梦断忆
2017-11-06 13:15:49
##DP + 滚动数组优化空间
这道题卡了差不多一个上午,思维难度灰常大,代码极简;
##题意,求波动数列
**首先我们必须要搞清楚3个性质**
>- First: 在一个波动数列中,若两个 i 与 i+1 不相邻,那么我们直接交换这两个数字就可以组成一个新的波动数列;
举个栗子: 5 2 3 1 4
4 2 3 1 5
>- Second: 把波动数列中的每个数字Ai 变成 (N+1)-Ai 会得到另一个波动数列,且新数列的山峰与山谷情况相反;
举个栗子: 1 4 2 5 3 (用 6 - 每个数) 1是山谷,4是山峰,后面类推
5 2 4 1 3 这个数列也是波动的 ,且 5是山峰,2是山谷;
>- Third: 波动序列有对称性。
栗子:1 4 2 5 3 to 3 5 2 1 4
这样我们的DP方程可以写成是:DP[I][J]表示 选 1 To I 这些数字,第一个数为山峰(山峰山谷比较形象),且第一个数为 J;
答案就是 ∑ DP[N][j] (j = 1 to N)
如何转移?这里我先上代码;
#DP[i][j]=DP[i][j-1]+DP[i-1][i-j+1];
##首先,我每次求 j作序列头,且表示山峰
由性质一可知,当j与j-1不相邻的时候,j作为头所有的方案数与j-1作为头的方案数相同,于是就有DP[I][J]=DP[I][J-1];
对于DP[i][j]+=DP[i-1][i+j-1];就是当j 与 j-1相邻时的情况;
**我们可以这么想,我第一个数选择了J 并且定义为山峰,那我第二个数j-1必定为山谷,后面的数属于[1,j-1]和[j+1,i];
###此时问题转化成了求 i-1个数,j-1为头,但是j-1 为山谷的方案数,由性质2可知,j-1作山谷和作山峰的方案数相同;
现在的问题就是,此时的区间和我DP方程的区间意义不同;
###没关系;因为山峰与山谷是相对位置关系,将[j+1,i]区间的每个数都减一,这样是不改变相对大小关系的,并且此时就符合我们的方程了;
另外,我DP[i-1][j-1]表示的是J-1为山顶时的个数,为了让其表示J-1为山谷的情况,要改成DP[i-1][(i-1+1)-(j-1)];
这样就得到了我们的转移方程,我们可以用滚动数组优化空间;
贴代码:
```cpp
cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
int f[2][MAXN]; //f[i][j]表示选前i个数,j是第一个数且为山峰;
int n,mod;
int main(){
scanf("%d%d",&n,&mod);
f[0][2]=1;
for(int i=3;i<=n;i++)
for(int j=2;j<=i;j++){
f[i&1][j]=(f[i&1][j-1]+f[(i-1)&1][i-j+1])%mod;}
//f[i][j]=f[i][j-1](把j 与 j-1直接交换掉,且j-1保证为山峰)+f[i-1][(i-1+1)-(j-1)]
//后面的式子表示,去掉 j ,让j-1当数列首位,则j-1保证为山谷,此时我们只构造了j-1为山峰的情况,用i-1+1-(j-1)即可;
int ans=0;
for(int j=2;j<=n;j++){
ans=(ans+f[n&1][j])%mod;
}
printf("%d",(ans<<1)%mod);
}
```