题意: 合唱队一共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],并且l后入的方案数dp[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的情况也类似.转移很简单
#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];
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
;
}
