A - 地精部落 (DP)

时间:2024-08-18 23:04:08

题目链接:https://cn.vjudge.net/contest/281960#problem/A

题目大意:中文题目。

具体思路:首先,如果有一段是山谷的话,那么这一段中也能用来表示山峰,只要将每一个的高度用N减一下,这样就形成了一个山峰。我们通过一个二维数组,dp[i][j]代表长度为i,第一位高度在[1,j]的满足山峰的方案数,我们就可以求出另一个表达式dp[i][j]=dp[i][j-1]+dp[i-1][j-1].(注意第一个i和第二个i不相同)这个怎么理解呢?首先dp[i-1][j]这个比较好理解,就是把原来长度已经存在的是山峰的加上,另外,我们需要把原来长度是i-1,首位是j-1并且是山谷的方案数求出来=dp[i-1][i-j+1](山谷和山峰是相对的)=dp[i][i-j].

dp[i][j]=dp[i][j-1]+f[i-1][j-1]=dp[i][j-1]+dp[i-1][i-1-(j-1)+1]=dp[i][j-1]+dp[i-1][i-j+1].

AC代码:

 #include<iostream>
#include<stdio.h>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
# define ll long long
const int maxn = 1e5+;
ll a[][maxn];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
a[][]=;
int tmp=;
for(int i=; i<=n; i++)
{
tmp^=;
for(int j=; j<=i; j++)
{
a[tmp][j]=(a[tmp][j-]+a[tmp^][i-j])%m;
}
}
printf("%lld\n",(a[tmp][n]*)%m);
return ;
}