codeforces 466D

题意：

给定n个数，你要选一些区间，每次区间+1，把这n个数都变成h

对任意两个区间,L1!=R1且L2!=R2

题解：

考虑每个位置只能不放，放一个区间左端点，放一个区间右端点，放一个左端点和一个右端点；

因此我们dp(i,j)表示到第i个，i和i+1之间被j个区间覆盖的方案数

讨论一下四种情况转移即可

#include<bits/stdc++.h>
#define ll long long
#define maxn 2005
using namespace std;
const ll mod = 1000000007;
int n,h;
int a[maxn];
ll dp[maxn][maxn];
int main()
{
    scanf("%d%d",&n,&h);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]),a[i]=h-a[i];
    for(int i=1;i<=n;++i)if(a[i]<0)
    {
        puts("0");exit(0);
    }
    a[0]=0;
    dp[0][0]=1;
    for(int i=0;i<=n;++i)
    {
        dp[i+1][a[i+1]]=(dp[i+1][a[i+1]]+dp[i][a[i+1]])%mod;
        dp[i+1][a[i+1]-1]=(dp[i+1][a[i+1]-1]+dp[i][a[i+1]-1]*a[i+1])%mod;
        dp[i+1][a[i+1]]=(dp[i+1][a[i+1]]+dp[i][a[i+1]-1])%mod;
        dp[i+1][a[i+1]-1]=(dp[i+1][a[i+1]-1]+dp[i][a[i+1]]*a[i+1])%mod;
    }
    printf("%I64d
",dp[n+1][0]);
    return 0;
}