正題

題目鏈接:https://www.luogu.org/problem/P2467

---

題目大意

求長(zhǎng)度為$n$的波動(dòng)序列的個(gè)數(shù)。

---

解題思路

我們先考慮第一個(gè)是上升的，然后乘2即可。

設(shè)$f_{i,j}$表示填$1～i$個(gè)，最前面的是$j$的個(gè)數(shù)。然后我們只要是$1～i?j+1$，當(dāng)然可以填$i$那么一定可以填$i+1$，所以有遞推方程$$f_{i,j}=f_{i,j?1}+f_{i?1,i?j+1}$$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; ll n,XJQ,f[2][4300],ans; int main() {scanf("%lld%lld",&n,&XJQ);f[0][2]=1;for(ll i=3;i<=n;i++){//memset(f[i&1],0,sizeof(f[i&1]));for(ll j=2;j<=i;j++){f[i&1][j]=(f[i&1][j-1]+f[~i&1][i-j+1])%XJQ;(ans+=f[i&1][j]*(i==n))%=XJQ;}}printf("%lld",(ans<<1)%XJQ); }

總結(jié)

以上是生活随笔為你收集整理的P2467-[SDOI2010]地精部落【dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。