[JXOI2017]数列

题面描述

求满足题目中限制条件的合法填数数量

题解

我不会推性质，只好写一个状压得 \(60\) 暴力分

我们发现题目中得状态必须和位置与至于有关，不妨考虑状态 \(f_{i,l,r}\) 代表在位置 \(i\) 取值范围为 \([l,\ r]\) 得方案数，考虑这个状态如何转移出去 我们发现 \(A_{i-1}\) 和 \(A_i\) 都不会超过这个值域，我们讨论一下他们的大小

当 \(A_i\ =\ A_{i-1}\ = l\) 时，\(A_{i+1}\in [l,\ l]\)

当 \(l < A_i\ \le\ A_{i-1}\ < r\) 时，\(A_{i+1}\in [l,\ A_{i-1}]\)

当 \(l < A_{i-1}\ \le\ A_i\ < r\) 时，\(A_{i+1}\in [A_{i-1},\ r]\)

当 \(A_i\ =\ A_{i-1}\ = r\) 时，\(A_{i+1}\in [r,\ r]\)

因此我们可以通过枚举 \(A_{i-1}\) 的取值确定下一部分的值

#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 50+5, M = 150+5, P = 998244353;
int n, a[N];
int f[N][M][M];
int dp(int p, int l, int r)
{
    if(p == n+1) return f[p][l][r] = 1;
    int &ret = f[p][l][r]; if(~ret) return ret; ret = 0;
    for(int i = max(l, 1); i <= min(r, a[p]); ++i) // 枚举 A_i-1 的值
        if(i == l||i == r) ret = (ret+dp(p+1, i, i))%P;
        else ret = (((ret+dp(p+1, l, i))%P+dp(p+1, i, r))%P-dp(p+1, i, i)+P)%P; // 减去重复的
    return ret;
}
int main()
{
    n = read(); memset(f, -1, sizeof(f));
    for(int i = 1; i <= n; ++i) a[i] = read();
    printf("%d\n", dp(1, 0, 151));
    return 0;
}