首页 > 代码库 > Codeforces Round #266 (Div. 2) D. Increase Sequence

Codeforces Round #266 (Div. 2) D. Increase Sequence

2024-07-22 19:57:25   221人阅读

Peter has a sequence of integers a1,?a2,?...,?an. Peter wants all numbers in the sequence to equalh. He can perform the operation of "adding one on the segment[l,?r]": add one to all elements of the sequence with indices froml tor (inclusive). At that, Peter never chooses any element as the beginning of the segment twice. Similarly, Peter never chooses any element as the end of the segment twice. In other words, for any two segments[l1,?r1] and[l2,?r2], where Peter added one, the following inequalities hold:l1?≠?l2 andr1?≠?r2.

How many distinct ways are there to make all numbers in the sequence equal h? Print this number of ways modulo 1000000007 (109?+?7). Two ways are considered distinct if one of them has a segment that isn‘t in the other way.

Input

The first line contains two integers n,?h(1?≤?n,?h?≤?2000). The next line containsn integersa1,?a2,?...,?an(0?≤?ai?≤?2000).

Output

Print a single integer — the answer to the problem modulo 1000000007 (109?+?7).

Sample test(s)
Input
3 2
1 1 1
Output
4
Input
5 1
1 1 1 1 1
Output
1
Input
4 3
3 2 1 1
Output
0
题意：选择若干个不重复的区间执行+1操作，求有多少种方法使得序列都是m
思路：dp[i][open]表示到第i个后左边还有多少个未匹配右括号的个数，另外还有一篇不错的题解：参考；引用：
Lets use dynamic programming to solve this problem. dp[i][opened] — the number of ways to cover prefix of array 1..i by segments and make it equal to h and remain after i-th element opened segments that are not closed.
Consider all possible variants opening/closing segments in each position:- ] closing one segment- [ opening one new segment- [] adding one segment with length 1- ][ closing one opened segment and opening a new one- - do nothing
Lets understand how to build dynamic. It is obviously to understand that a[i]?+?opened can be equal h or h?-?1. Otherwise, number of such ways equals 0.
Consider this two cases separately:
1) a[i]?+?opened?=?hIt means that number of opened segments after i-th as max as possible and we can’t open one more segment in this place. So there are two variants:- [ Opening a new segment. If only opened?>?0. dp[i][opened] += dp[i-1][opened + 1]- - Do nothing. dp[i][opened] += dp[i-1][opened]
Other variants are impossible because of summary value of a[i] will be greater than h(when segment is finishing in current position — it increase value, but do not influence on opened, by the dynamic definition.
2) a[i]?+?opened?+?1?=?h Here we consider ways where i-th element has been increased by opened?+?1 segments, but after i-th remain only opened not closed segments. Therefore, there are next variants:- ] — closing one of the opened segments(we can do it opened?+?1 ways).dp[i][opened] += dp[i-1][opened + 1] * (opened + 1) - [] — creating 1-length segment. dp[i][opened] += dp[i-1][opened] - ][ — If only opened?>?0. Amount of ways to choose segment which we will close equals opened.dp[i][opened] += dp[i-1][opened] * opened
Start values — dp[1][0] = (a[1] == h || a[1] + 1 == h?1:0); dp[1][1] = (a[1] + 1 == h?1:0)
Answer — dp[n][0].
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn = 2010;
#define mod 1000000007

ll dp[maxn][maxn];
int a[maxn];

inline void add(ll &a, ll b) {
	a += b;
	a %= mod;
}

int main() {
	int n, h;
	cin >> n >> h;
	
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	dp[1][0] = (a[1] == h || a[1]+1 == h ? 1 : 0);
	dp[1][1] = (a[1]+1 == h ? 1 : 0);

	for (int i = 2; i <= n+1; i++)
		for (int open = max(0, h-a[i]-1); open <= min(h-a[i], i); open++) {
			if (open + a[i] == h) {
				add(dp[i][open], dp[i-1][open]);
				if (open > 0)
					add(dp[i][open], dp[i-1][open-1]);
			}

			if (open + a[i] + 1 == h) {
				add(dp[i][open], dp[i-1][open+1]*(open+1));
				add(dp[i][open], dp[i-1][open]);
				add(dp[i][open], dp[i-1][open]*open);
			}
		}
	cout << dp[n][0] << endl;
	return 0;
}


Codeforces Round #266 (Div. 2) D. Increase Sequence


联系
我们