题解 P4063 【[JXOI2017]数列】

· · 题解

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

考虑送后往前构造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]或者不等于。若不等于，则

设$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;
}