CF1763D

标签：ch int CF1763D ll ans dp define

Valid Bitonic Permutations - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意转化一下：先考虑如何构造一个双调的序列。

本题的解题核心是：如何构造出双调的序列？（主要是这个技巧要知道）

那么如何构造呢？

首先来看 1 ，可以放在最左边，也可以放在最右边。

               2，同理，在1的基础上，可以放在左边，可以放在右边

其他数也是一样。(主要是这个构造的思想，没做过构造一个双调的序列不容易想出来)

所以对于 数字 num 来说，可以放在L位置，或者R位置

这便可以用dfs(num,L,R)来进行记忆化搜索dp。

根据L，R可以推出 num 便可以优化 num 维度

这便是构造出普通的双调的序列的方案数的dfs

ll dfs(int l,int r)
{
    int num=(l-1)+(n-r)+1;
    if(l==r&&l!=1&&l!=n) return 1; 
    if(dp[l][r]!=-1) return dp[l][r];
    ll ans=0;
    ans=(ans+dfs(l+1,r))%MOD;
    ans=(ans+dfs(l,r-1))%MOD;
    return dp[l][r]=ans;
}

接下来在把题目的要求放进去即可：

注意 L==R的地方不能是 1 和 n，因为这两种情况是单峰序列(题目要求也有提及)

// LUOGU_RID: 108705056
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
const int N=110;
const ll MOD=1e9+7;
//const int inf=1e9;
//const ll INF=1e18;
int T,n,posa,posb,x,y;
ll dp[N][N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int check(int pos,int num)
{
    if(pos==posa) return num==x;
    else if(pos==posb) return num==y;
    return 1;
}
ll dfs(int l,int r)
{
    int num=(l-1)+(n-r)+1;
    if(l==r) 
    {
        if(check(l,num)&&l!=1&&l!=n) return 1;
        return 0;
    }
    if(dp[l][r]!=-1) return dp[l][r];
    ll ans=0;
    ans=(ans+check(l,num)*dfs(l+1,r))%MOD;
    ans=(ans+check(r,num)*dfs(l,r-1))%MOD;
    return dp[l][r]=ans;
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0);
    T=read();
    while(T--)
    {
        n=read(),posa=read(),posb=read(),x=read(),y=read();
        memset(dp,-1,sizeof(dp));
        printf("%lld\n",dfs(1,n));
    }
    return 0;
}

 

标签：ch,int,CF1763D,ll,ans,dp,define
From： https://www.cnblogs.com/Willette/p/17364562.html