AquaRio 的博客

AquaRio 的博客

题解 P2467 【[SDOI2010]地精部落】

posted on 2019-06-15 16:57:13 | under 题解 |

没用滚动数组瞎写居然没有被卡空间!!!!

这题在省选题里还是算比较简单的
蒟蒻第一次写题解


题意分析

首先我们根据题意

·这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的位置关系

  1. 若j与j-1不相邻
    互换j与j-1,仍然得到的是一族合法的序列,且以j-1开头。具体为什么...自己写几个就会发现规律~
    所以 f(i,j)+=f(i,j-1)

  2. 若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;  //别忘记模了
}