CodeforcesRound#266(Div.2)D.IncreaseSequence_html/css

3 21 1 1

5 11 1 1 1 1

4 33 2 1 1

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 #include #include #include 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;}