2020-2021:teams:legal_string:jxm2001:contest:arc_127
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:arc_127 [2021/09/27 16:27] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:arc_127 [2021/09/27 16:52] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 116: | 行 116: | ||
| 不难构造出令最后优先队列中剩余元素尽可能大的方案：第 $i$ 次 $\text{push}$ 元素 $i$。 | 不难构造出令最后优先队列中剩余元素尽可能大的方案：第 $i$ 次 $\text{push}$ 元素 $i$。 | ||
| - | 假定上述方案中 | + | 假定上述方案最后得到的优先队列的元素为 $a_1\lt a_2\lt \cdots a_{n-m}$，被删除的元素为 $b_1\lt b_2\lt \cdots b_m$。 |
| + | |||
| + | 对任意一个方案，假定最后得到的优先队列的元素为 $x_1\lt x_2\lt \cdots x_{n-m}$，被删除的元素为 $y_1\lt y_2\lt \cdots y_m$。 | ||
| + | |||
| + | 不难发现，一定有 $x_i\le a_i$。下面证明满足该条件的所有方案均为合法方案。 | ||
| + | |||
| + | 考虑构造，第 $a_i$ 次 $\text{push}$ 元素 $x_i$，第 $b_i$ 次 $\text{push}$ 元素 $y_i$。 | ||
| + | |||
| + | 于是问题等价与找到 $x_i\le a_i$ 的递增序列数，可以 $O(n^2)$ $\text{dp}$ 计算。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=5005,mod=998244353; | ||
| + | int st[MAXN],dp[2][MAXN]; | ||
| + | int main(){ | ||
| + | int n=read_int(),m=read_int(),top=0,pos=0; | ||
| + | _for(i,0,n+m){ | ||
| + | int x=read_int(); | ||
| + | if(x==1) | ||
| + | st[++top]=++pos; | ||
| + | else | ||
| + | top--; | ||
| + | } | ||
| + | pos=0; | ||
| + | dp[0][0]=1; | ||
| + | _rep(i,1,top){ | ||
| + | pos=!pos; | ||
| + | mem(dp[pos],0); | ||
| + | int s=dp[!pos][0]; | ||
| + | _rep(j,1,st[i]){ | ||
| + | dp[pos][j]=s; | ||
| + | s=(s+dp[!pos][j])%mod; | ||
| + | } | ||
| + | } | ||
| + | int ans=0; | ||
| + | _rep(i,1,n) | ||
| + | ans=(ans+dp[pos][i])%mod; | ||
| + | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/arc_127.1632731222.txt.gz · 最后更改: 2021/09/27 16:27 由 jxm2001
