正題

---

題目大意

長度為$n$的序列，$m$個位置要求兩邊都比他大，$k$個位置要求兩邊都比他小。求序列個數(shù)。

---

解題思路

若第$x$個位置為山峰，那么$a_{x?1}<a_x>a_{x+1}$，我們用$u{p}_i$表示第$i$個位置與前面數(shù)的大小關系。

然后用$f_{i,j}$表示前$i$個數(shù)是$1～i$，最后一個為$j$時的方案數(shù)，然后根據(jù)$u{p}_i$轉(zhuǎn)移即可。

---

$code$

#include<cstring> #include<algorithm> #define ll long long using namespace std; const ll XJQ=1e9+7,N=5100; ll n,m,k,up[N],f[N][N],ans,sum[N]; bool flag; int main() {scanf("%lld%lld%lld",&n,&m,&k);for(ll i=1;i<=m;i++){ll x;scanf("%lld",&x);x++; // if(up[x]&&up[x]==1||up[x+1]&&up[x+1]==2) // {flag=1;break;}up[x]=2;up[x+1]=1;}for(ll i=1;i<=k;i++){ll x;scanf("%lld",&x);x++; // if(up[x]&&up[x]==2||up[x+1]&&up[x+1]==1) // {flag=1;break;}up[x]=1;up[x+1]=2;}if(flag){putchar('0');return 0;}f[1][1]=1;for(ll i=2;i<=n;i++){for(ll j=1;j<i;j++)sum[j]=(sum[j-1]+f[~i&1][j])%XJQ;if(!up[i])for(ll j=1;j<=i;j++)f[i&1][j]=sum[i-1];else if(up[i]==1)for(ll j=1;j<=i;j++)f[i&1][j]=sum[j-1];elsefor(ll j=1;j<=i;j++)f[i&1][j]=(sum[i-1]-sum[j-1]+XJQ)%XJQ;}for(ll i=1;i<=n;i++)(ans+=f[n&1][i])%=XJQ;printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的nssl1447-小智的糖果【dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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