`
阿尔萨斯
  • 浏览: 4108126 次
社区版块
存档分类
最新评论

Codeforces 466D Increase Sequence(dp+组合数学)

 
阅读更多

题目链接:Codeforces 466D Increase Sequence

题目大意:给定一个序列,现在可以选中一段区间,使得整段区间上每个位置数加1,要求最后每个位置都为h,并且选中的区间不能有相同l或则r。

解题思路:因为每个位置最多有一个起始和一个终止(区间)。

  • aiai+1差的绝对值超过1,则肯定是不行的,
  • ai+1ai=1,那么一定要从i+1的位置新起一段区间
  • ai+1ai=1,那么一定要在i+1的位置上终止一段区间,C(1ai)
  • ai+1ai=0,可以不变,也可以终止并新起一段。
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 2005;
const ll mod = 1e9+7;

int N, H, arr[maxn];

int solve () {
    N++;
    ll ret = 1;

    for (int i = 1; i <= N; i++) {
        int t = arr[i] - arr[i-1];

        if (t > 1 || t < -1)
            return 0;
        else if (t == 0)
            ret = ret * (arr[i] + 1) % mod;
        else if (t == -1)
            ret = ret * arr[i-1] % mod;
    }
    return ret;
}

int main() {
    scanf("%d%d", &N, &H);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
        arr[i] = H - arr[i];
    }
    printf("%d\n", solve());
    return 0;
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics