自动搬运

查看原文

来自洛谷，原作者为

	VSEJGFB **

搬运于2025-08-24 21:56:05，当前版本为作者最后更新于2018-04-09 22:18:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

发一个不一样的做法~~~~

考虑送后往前构造$A[i]$

最后两个:$A[n],A[n-1]$是可以分别在$1-r[n],1-r[n-1]$中任意选.

然后发现$A[n-2]$不能在$A[n]$与$A[n-1]$之间 但可以是$A[n]$

因为必须满足$A[n-2]> A[n-1] > A[n]$或者$A[n-2] < A[n-1] < A[n]$或三者相等

同理$A[n-3]$也满足此条件且还不能在$A[n-2]$与$A[n-1]$之间(因为上面条件限制所以$A[n-1]$也不行)。

同理$A[n-k]$……

当从后向前选至$A[i]$时，不能选的值一定为一个区间。

设$d(bt,tp,i)$为当前选择$A[i]$,不能选的区间为$[bt,tp]$

因为$A[i+1]\in [bt,tp]$所以若$A[i]=k$则由$d(k,tp,i-1),k<bt$或$d(bt,k,i-1),k>tp$转移过来。（因为$A[i-1]$不能在$A[i]$与$A[i+1]$之间。）

但有一种特殊情况即$A[n]=A[n-1]=A[n-2]=...=A[n-k]$时$A[n-k-1]$可以等于$A[n-k]$或者不等于。若不等于，则 $A[n-k-2]$可以等于$A[n-k]$（比如$A[n-2]$可以等于$A[n]$)而且此时必定$bt=tp=A[n-k]$所以bt或tp不在$A[n-k-2]$的不可取范围内。

设$d(bt,tp,i,o)$，$o=1$时满足这种情况，$o=0$则不满足。

边界$d(bt,tp,0,o)=1$.

状态$O(nr_i^2)$个，转移$O(r_i)$ 记忆化搜索实际上没那么多状态

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int p=998244353;
const int N=52,R=152;
int d[R][R][N][2],r[N];
int dp(int bt,int tp,int cur,int o){
    if(cur==0) return 1;
    int bot=min(r[cur]+1,bt);
    int &ans=d[bt][tp][cur][o];
    if(ans>-1) return ans;
    ans=0;
    int k=0;
    if(bt==tp&&o){
        k=1,o=0;  //k=1时tp-1或bt+1就没有把tp或bt包含在不可取范围
        if(bt<=r[cur]) ans=(ans+dp(bt,tp,cur-1,1))%p;
    }
    for(int i=1;i<bot;i++) ans=(ans+dp(i,tp-k,cur-1,o))%p;
    for(int i=tp+1;i<=r[cur];i++) ans=(ans+dp(bt+k,i,cur-1,o))%p;
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&r[i]);
    memset(d,-1,sizeof(d));
    int ans=0;
    for(int i=1;i<=r[n];i++){
        for(int j=1;j<=r[n-1];j++){
            int k=ans;
            if(i==j) ans=(ans+dp(i,j,n-2,1))%p; 
            else if(i<j) ans=(ans+dp(i+1,j,n-2,0))%p;
            else if(i>j) ans=(ans+dp(j,i-1,n-2,0))%p;//i+1或i-1就没有把A[n]包含在不可取范围
        }
    }
    printf("%d\n",ans);
    return 0;
}