题解：CF466D Increase Sequence

· · 题解

题意

给定一个长度为 n 数组 A，可选择若干区间对其中的元素加一，满足任意两个的区间的端点不得重合。求把所有元素变成 k 的方案数。

思路

有区间加，容易想到在差分数组 D 上计算。显然数组中不能有大于 k 的元素，差分数组中（除首项）也不能有绝对值大于 1 的元素。选择区间 [l, r] 加一的效果是使 D_l 加一，D_{r + 1} 减一。所以使得所有值等于 k 的本质就是在差分数组中选择一些 -1 和 1 配对，且 -1 必须在 1 的左边。只需从左往右遍历，记录遇到的 -1 的数量 c。按 D_i 的值分类讨论：

最后检查一下 c，因为 r + 1 是可以取到 n + 1 的，c 有剩下意味D_{n + 1} 必须来跟它匹配，所以要求 c \le 1，至多只能匹配一个，再多就是非法了。

代码

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 2005, Mod = 1e9+7;
int Diff[N];

void Assert(bool f) {if(f)  cout<<0<<endl, exit(0);}

int main() {
    int n, k;   cin>>n>>k, Diff[0]=k;
    for(int i=1;i<=n;i++)   cin>>Diff[i], Assert(Diff[i]>k);
    for(int i=n;i>=1;i--)   Diff[i]-=Diff[i-1], Assert(abs(Diff[i])>1);

    int Ans=1, Cnt=0;
    for(int i=1;i<=n;i++)
        if(Diff[i]==-1) Cnt++;
        else if(Diff[i]==1) Ans=(ll)Ans*Cnt%Mod, Cnt--;
        else    Ans=(ll)Ans*(Cnt+1)%Mod;

    cout<<(Cnt>1? 0:Ans)<<endl;
    return 0;
}