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

本文主要是介绍Codeforces 466D Increase Sequence(dp+组合数学)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：Codeforces 466D Increase Sequence

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

解题思路：因为每个位置最多有一个起始和一个终止（区间）。

• ai和ai+1差的绝对值超过1，则肯定是不行的，
• ai+1−ai=1,那么一定要从i+1的位置新起一段区间
• ai+1−ai=−1，那么一定要在i+1的位置上终止一段区间，C(1ai)
• ai+1−ai=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;
}

这篇关于Codeforces 466D Increase Sequence(dp+组合数学)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---