[Codevs] 1523 地精部落

1523 地精部落

省队选拔赛

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 大师 Master

 

题目描述 Description

传说很久以前，大地上居住着一种神秘的生物：地精。 
地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为 N 的山脉 H可分为从左到右的 N 段，每段有一个独一无二的高度 Hi，其中Hi是1到N 之间的正整数。 
如果一段山脉比所有与它相邻的山脉都高，则这段山脉是一个山峰。位于边缘的山脉只有一段相邻的山脉，其他都有两段（即左边和右边）。 
类似地，如果一段山脉比所有它相邻的山脉都低，则这段山脉是一个山谷。 
地精们有一个共同的爱好——饮酒，酒馆可以设立在山谷之中。地精的酒馆不论白天黑夜总是人声鼎沸，地精美酒的香味可以飘到方圆数里的地方。 
地精还是一种非常警觉的生物，他们在每座山峰上都可以设立瞭望台，并轮流担当瞭望工作，以确保在第一时间得知外敌的入侵。 
地精们希望这N 段山脉每段都可以修建瞭望台或酒馆的其中之一，只有满足这个条件的整座山脉才可能有地精居住。 
现在你希望知道，长度为N 的可能有地精居住的山脉有多少种。两座山脉A和B不同当且仅当存在一个 i，使得 Ai≠Bi。由于这个数目可能很大，你只对它除以P的余数感兴趣。

 

输入描述 Input Description

输入仅含一行，两个正整数 N,P。 

输出描述 Output Description

输出仅含一行，一个非负整数，表示你所求的答案对P取余之后的结果。

样例输入 Sample Input

4 7

样例输出 Sample Output             

3

数据范围及提示 Data Size & Hint

共有10 种可能的山脉，它们是：
1324 1423 2143 2314 2413
3142 3241 3412 4132 4231 

【数据规模和约定】
对于 20%的数据，满足 N≤10；
对于 40%的数据，满足 N≤18；
对于 70%的数据，满足 N≤550；
对于 100%的数据，满足 3≤N≤4200，P≤10⁹。

分析 Analysis

我相信这道题一定有组合数学的解法（然而我自己找不到）

主流解法动态规划。

首先用DP[i][j]表示一种状态的方案数，该状态的数集有i个数（可以意淫为1~i），其中该状态子序列的第一个数取值范围为1~j

PS：这么意淫的前提是题目明确说明山峰高度是1~n的排列，因此显然1~(j-1)均小于j

同时约定表示所代表的方案均为A₁ < A₂也就是开头呈上升趋势，因此有DP[i][j] = DP[i][j-1]+DP[i-1][i-j]

DP[i][j-1]表示同样的状态下序列中第一个数取值范围为1~(j-1)时的方案数

DP[i-1][i-j]表示取走一个数之后的状态，此时数集中只剩i-1个数，而此时序列的第二个数范围必为j+1 ~ i，共i-j个数（因为已经约定序列开头上升了，所以第二个数必须比j大）

PS：我写这篇博客唯一的目的就是好好解释清楚这个转移方程

代码 Code

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int dp[5000][5000];

int main(){
    
    int n;
    scanf("%d",&n);
    
    dp[1][1] = 1;
    for(int i = 2;i <= n;i++){
        for(int j = 1;j <= i;j++){
            dp[i][j] = dp[i][j-1]+dp[i-1][i-j];
        }
    }
    
    printf("%d",dp[n][n]);
    
    return 0;
}

评价&分类 Rank&Sort

思维题. >> 动态规划