Codeforces ラウンド #266 (ディビジョン 2) D. Sequence_html/css_WEB-ITnose を増やす

Peter は、一連の整数 a1、?a2、?...、?an を持っています。ピーターは、シーケンス内のすべての数値が等しくなることを望んでいます。彼は、「segment[l,?r] に 1 を加算する」という操作を実行できます。つまり、l から r (両端を含む) までのインデックスを持つシーケンスのすべての要素に 1 を加算します。その際、Peter はセグメントの開始として要素を 2 回選択することはありません。同様に、Peter はセグメントの終わりとして要素を 2 回選択することはありません。言い換えると、Peter が 1 を加えた任意の 2 つのセグメント [l1,?r1] と [l2,?r2] に対して、次の不等式が成り立ちます: l1?≠?l2 andr1?≠?r2。

異なる方法はいくつありますか?シーケンス内のすべての数値を h に等しくするには?このウェイ数を法 1000000007 (109?+?7) として出力します。 2 つの方法の一方に他方にはないセグメントがある場合、2 つの方法は区別されると見なされます。

入力

最初の行には 2 つの整数 n,?h(1?≤?n,?h?≤? 2000年）。次の行には、n 個の整数 a1,?a2,?...,?an(0?≤?ai?≤?2000) が含まれています。

出力

単一の整数を出力します。問題の答え、モジュロ 1000000007 (109?+?7)。

サンプル テスト

入力

3 21 1 1

出力

入力

5 11 1 1 1 1

出力

入力

4 33 2 1 1

出力

0题意：选择若干个不重复的区间执行+1操作，求有多少种方法使得序列都是m思路：dp[i][open]表示到第i个后左边还有多少个未匹配右括号的个数，另外还有一篇不错的题解：参考；引用：<p></p><p>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.</p><p>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</p><p>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.</p><p>Consider this two cases separately:</p><p>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]</p><p>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.</p><p>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</p><p>Start values ? dp[1][0] = (a[1] == h || a[1] + 1 == h?1:0); dp[1][1] = (a[1] + 1 == h?1:0)</p><p>Answer ? dp[n][0].</p><p></p><strong></strong><pre name="code" class="n">#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>typedef long long ll;using namespace std;const int maxn = 2010;#define mod 1000000007ll 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;}