题目描述

难度分:$1404$

输入$n(1 \leq n \leq 10^5)$和两个长为$n$的数组$b$和$c$$(1 \leq b[i],c[i] \leq 10^9)$。

构造数组$a$，满足$a[i]$都是正整数，且：

• $b[i] = max(a[1], a[2], …, a[i])$，即数组$a$的前缀最大值。
• $c[i] = max(a[i], a[i+1], …, a[n])$，即数组$a$的后缀最大值。

问：有多少个符合要求的数组$a$？由于结果可能非常大，需要对结果模$10^9+7$。

如果不存在这样的数组$a$，输出$0$。

输入样例$1$

5
1 3 3 3 3
3 3 2 2 2

输出样例$1$

4

输入样例$2$

5
1 1 1 2 2
3 2 1 1 1

输出样例$2$

0

输入样例$3$

10
1 3776 3776 8848 8848 8848 8848 8848 8848 8848
8848 8848 8848 8848 8848 8848 8848 8848 3776 5

输出样例$3$

884111967

输入样例$4$

1
17
17

输出样例$4$

1

算法

动态规划

这个题看着很像要用DP解决的类型（计数类问题一般就是用DP或者组合数学的方法来统计，或者二者都有），结合$n \leq 10^5$的信息，应该是个线性DP。

状态定义

$dp[i]$表示的是考虑前$i$个元素的情况下，能够构造出来的数组数量，因此答案为$dp[n]$。

状态转移

$base$ $case$：$dp[0]=1$，空数组算一种方案。

很显然，$b$数组是个单调不降的数组，$c$数组是个单调不增的数组。

1. 如果$b[i] \neq b[i-1]$，说明$b[i]$是第一次出现，$a[i]$必须要是$b[i]$，只有一种方式，但考虑到$c[i]$的约束，如果$b[i] \gt c[i]$，就与$c[i]=max_{j=i}^{n}a[j]$矛盾了，直接返回$0$；否则状态转移方程为$dp[i]=dp[i-1]$。
2. 如果$b[i] = b[i-1]$，说明$a[i]$进入了一个平台，不考虑后缀最大值数组$c$的话，由于前面已经出现过$b[i]$这个值，当前位置$i$可以是$[1,b[i]]$区间内的任何数。但此时需要考虑$c[i]$的约束，对称的：$c[i] \neq c[i+1]$时，$c[i]$是第一次出现，$i$位置只能是$c[i]$，状态转移方程为$dp[i]=dp[i-1]$。$c[i]=c[i+1]$时，$c[i]$进入了平台，由于后面$(i,n]$已经出现过$c[i]$这个值，所以当前位置可以是区间$[1,c[i]]$内的任何数，综合$b[i]$的约束，可以取值的区间就是$[1,min(b[i],c[i])]$，状态转移方程为$dp[i]=min(b[i],c[i]) \times dp[i-1]$。

复杂度分析

时间复杂度

遍历了遍原数组$a$进行线性DP，时间复杂度为$O(n)$。

空间复杂度

用两个变量$last$和$res$滚动，代替了DP数组，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 100010, MOD = 1e9 + 7;
int b[N], c[N], dp[N], n;

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    int last = 1, res = 0;
    for(int i = 1; i <= n; i++) {
        if(b[i] == b[i - 1]) {
            if(c[i] == c[i + 1]) {
                res = (LL)min(b[i], c[i])*last%MOD;
            }else {
                res = last;
            }
        }else {
            if(c[i] < b[i]) {
                puts("0");
                exit(0);
            }else {
                res = last;
            }
        }
        last = res;
    }
    printf("%d\n", res);
    return 0;
}