DP(区间专题五)

it2022-05-06  4

题意: 合唱队一共N个人,第i个人的身高为Hi米(1000<=Hi<=2000),并已知任何两个人的身高都不同。假定最终排出的队形是A 个人站成一排,为了简化问题,小A想出了如下排队的方式:他让所有的人先按任意顺序站成一个初始队形,然后从左到右按以下原则依次将每个人插入最终棑排出的队形中:

第一个人直接插入空的当前队形中。

对从第二个人开始的每个人,如果他比前面那个人高(H较大),那么将他插入当前队形的最右边。如果他比前面那个人矮(H较小),那么将他插入当前队形的最左边。

当N个人全部插入当前队形后便获得最终排出的队形。

>> face <<

Strategy: 区间dp or 记忆化搜索

状态: { d p [ l ] [ r ] [ 0 ] → 可 得 到 理 想 区 间 [ l , r ] , 并 且 l 后 入 的 方 案 数 d p [ l ] [ r ] [ 1 ] → 可 得 到 理 想 区 间 [ l , r ] 并 且 r 后 入 的 方 案 数 \begin{dcases}dp[l][r][0]\quad \to \quad 可得到理想区间[l, r],并且l后入的方案数\\[2ex] dp[l][r][1]\quad\to\quad 可得到理想区间[l, r]并且r后入的方案数\end{dcases} dp[l][r][0][l,r],ldp[l][r][1][l,r]r

目标: ( d p [ 1 ] [ n ] [ 0 ] + d p [ 1 ] [ n ] [ 1 ] ) % m o d (dp[1][n][0] + dp[1][n][1]) \% mod (dp[1][n][0]+dp[1][n][1])%mod

边界: d p [ i ] [ i ] [ 1 ] = 1 ; dp[i][i][1] = 1; dp[i][i][1]=1;

合法判断: 后插的数与之前的数满足一定的大小关系才能进行转移

转移方程: 区间dp, 枚举未知, 让所有能转移到该未知的状态来转移, 方程见上

attention:

状态的设计边界初始化为啥dp[i][i][1]不能等于1 ? hack: 1 1会输出2

双倍经验:

@author: jasonleft 区间dp #include <bits/stdc++.h> #include <bits/extc++.h> #define _rep(i, a, b) for (int i = (a); i <= (b); ++i) #define _rev(i, a, b) for (int i = (a); i >= (b); --i) #define _for(i, a, b) for (int i = (a); i < (b); ++i) #define _rof(i, a, b) for (int i = (a); i > (b); --i) #define ll long long #define db double #define oo 0x3f3f3f3f #define eps 0.00001 #define all(x) x.begin(), x.end() #define met(a, b) memset(a, b, sizeof(a)) #define what_is(x) cerr << #x << " is " << x << endl #define lowbit(x) x &(-x) using namespace std; const int maxn = 1e3 + 9; const int mod = 19650827; int dp[maxn][maxn][2], n, a[maxn]; int main() { ios::sync_with_stdio(0); cin >> n; _rep(i, 1, n) { cin >> a[i]; dp[i][i][0] = 1; } _rep(len, 2, n) { _rep(l, 1, n - len + 1) { int r = l + len - 1; dp[l][r][0] = (dp[l + 1][r][0] * (a[l] < a[l + 1]) + dp[l + 1][r][1] * (a[l] < a[r])) % mod; dp[l][r][1] = (dp[l][r - 1][0] * (a[r] > a[l]) + dp[l][r - 1][1] * (a[r] > a[r - 1])) % mod; } } cout << (dp[1][n][0] + dp[1][n][1]) % mod << endl; }

第一次回顾

状态很难想 可以从这里开始, 每个区间[l,r]都由两种方式转移过来, 一种是最后一个转移过来的是l, 另一种是最后一个转移过来的是r, 假设最后一个转移过来的是r, 那么转移之前的区间是[l,r-1], 这时我们就要讨论这个区间的最后一个转移过来的是谁了, 如果是l, 那么我们要满足新数大于a[l], 否则不能放右边, 如果是r-1,那么依旧要满足新数大于a[r-1], 这才能贡献到转移区间[l,r]最后一个是r的情况, 同理最后一个是l的情况也类似.转移很简单 /* * I Love Coding! * * .::::. * .::::::::. * ::::::::::: * ..:::::::::::' * '::::::::::::' * .:::::::::: * '::::::::::::::.. * ..::::::::::::. * ``:::::::::::::::: * ::::``:::::::::' .:::. * ::::' ':::::' .::::::::. * .::::' :::: .:::::::'::::. * .:::' ::::: .:::::::::' ':::::. * .::' :::::.:::::::::' ':::::. * .::' ::::::::::::::' ``::::. * ...::: ::::::::::::' ``::. * ````':. ':::::::::' ::::.. * '.:::::' ':'````.. */ #include <bits/stdc++.h> #include <bits/extc++.h> #define _rep(i, a, b) for (int i = (a); i <= (b); ++i) #define _rev(i, a, b) for (int i = (a); i >= (b); --i) #define _for(i, a, b) for (int i = (a); i < (b); ++i) #define _rof(i, a, b) for (int i = (a); i > (b); --i) #define ll long long #define db double #define oo 0x3f3f3f3f #define eps 0.00001 #define all(x) x.begin(), x.end() #define met(a, b) memset(a, b, sizeof(a)) #define id(x) ((x + 8)) #define what_is(x) cerr << #x << " is " << x << endl #define lowbit(x) x &(-x) const int maxn = 1e3 + 9; const int mod = 19650827; using namespace std; ll a[maxn], n, dp[maxn][maxn][2]; //dp[l][r][0] : r最后入lr区间 int main() { ios::sync_with_stdio(0); int n; cin >> n; _rep(i, 1, n) { cin >> a[i]; dp[i][i][1] = 1; } _rep(len, 2, n) { _rep(l, 1, n - len + 1) { int r = l + len - 1; dp[l][r][0] = (dp[l][r - 1][0] * (a[r] > a[r - 1]) + dp[l][r - 1][1] * (a[r] > a[l])) % mod; dp[l][r][1] = (dp[l + 1][r][0] * (a[l] < a[r]) + dp[l + 1][r][1] * (a[l + 1] > a[l])) % mod; } } cout << (dp[1][n][0] + dp[1][n][1]) % mod << endl; }

最新回复(0)