Luogu

BZOJ

分析

DP+九条可怜

考虑从后往前构造 $a$ 序列。

首先, $a_n$ 可以选择 $1\sim r_n$ , $a_{n-1}$ 可以选择 $1\sim r_{n-1}$ 。

手玩一下发现,从后往前选到某一个数时,不能填的值一定是一个区间。

设 $f[i][l][r]$ 表示选到第 $i$ 个数,不能选 $[l,r]$ 的方案数。

转移直接枚举填的值即可。

但是,可能会有 $a[i]=a[i+1]=...=a[n-1]=a[n]$ 的情况。多加一维 $0/1$ ,然后类似地进行转移。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50+10;
const int R=150+10;
const int mod=998244353;

int n,up[N];
int f[N][R][R][2];

inline void add(int& x,int y) { x=(x+y)%mod; }

inline int dfs(int p,int l,int r,int v) {
    if (!p) return 1;
    if (~f[p][l][r][v]) return f[p][l][r][v];
    int res=0,tmp=min(up[p]+1,l);
    if (l==r&&v) {
        if (l<=up[p]) add(res,dfs(p-1,l,r,1));
        for (re int i=1;i<tmp;++i) add(res,dfs(p-1,i,r-1,0));
        for (re int i=r+1;i<=up[p];++i) add(res,dfs(p-1,l+1,i,0));
    } else {
        for (re int i=1;i<tmp;++i) add(res,dfs(p-1,i,r,v));
        for (re int i=r+1;i<=up[p];++i) add(res,dfs(p-1,l,i,v));
    }
    return f[p][l][r][v]=res;
}

int main() {
    memset(f,-1,sizeof(f));
    n=read(); int ans=0;
    for (re int i=1;i<=n;++i) up[i]=read();
    for (re int i=1;i<=up[n];++i)
        for (re int j=1;j<=up[n-1];++j) {
            if (i==j) add(ans,dfs(n-2,i,j,1));
            else if (i<j) add(ans,dfs(n-2,i+1,j,0));
            else add(ans,dfs(n-2,j,i-1,0));
        }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 30 PM