【NOI2022省选挑战赛 Contest10 B】早该砍砍了(笛卡尔树)(DP)
早该砍砍了
题目链接:NOI2022省选挑战赛 Contest10 B
题目大意
给你一个序列,保证任意两个位置的数都不相同,你每次可以选择一个区间把里面的数都变成其中的最小值,问你操作若干次(可以不操作)之后序列的样子有多少种。
思路
考虑求出序列每个位置的“管辖范围”(这是这段范围里面的区间去的最小值都是它),这个不难用笛卡尔树求出。
然后我们因为它说序列每个位置的数都不一样,所以我们考虑 DP。
设
f
i
,
j
f_{i,j}
fi,j 为考虑了前
i
i
i 个序列的数的覆盖范围,然后当前最优覆盖到
j
j
j 的方案数。
然后你要想到一个数的覆盖区间不一定包括它自己(因为其实可能后面会有更小的把它给覆盖了,但是它还有一些旁边的覆盖的位置没有被覆盖)
然后 DP 即可。
代码
#include<cstdio>
#include<iostream>
#define ll long long
#define mo 1000000007
using namespace std;
int n, a[3001];
int minn[3001][15], pla[3001][15], log2_[3001];
ll f[3001][3001];
struct node {
int l, r, ls, rs;
}t[3001];
int rt;
int get_min(int l, int r) {
int k = log2_[r - l + 1];
if (minn[l][k] < minn[r - (1 << k) + 1][k]) return pla[l][k];
else return pla[r - (1 << k) + 1][k];
}
int build(int l, int r) {
if (l == r) {
t[l].l = l; t[r].r = r;
return l;
}
int now = get_min(l, r);
t[now].l = l; t[now].r = r;
if (l != now) t[now].ls = build(l, now - 1);
if (now != r) t[now].rs = build(now + 1, r);
return now;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), minn[i][0] = a[i], pla[i][0] = i;
for (int i = 1; i <= 14; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
if (minn[j][i - 1] < minn[j + (1 << (i - 1))][i - 1]) minn[j][i] = minn[j][i - 1], pla[j][i] = pla[j][i - 1];
else minn[j][i] = minn[j + (1 << (i - 1))][i - 1], pla[j][i] = pla[j + (1 << (i - 1))][i - 1];
log2_[0] = -1; for (int i = 1; i <= n; i++) log2_[i] = log2_[i >> 1] + 1;
rt = build(1, n);
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
ll sum = 0;
for (int j = t[i].l; j <= t[i].r; j++) {
sum = (sum + f[i - 1][j - 1]) % mo;
f[i][j] = (f[i][j] + sum) % mo;
}
for (int j = 0; j <= n; j++)
f[i][j] = (f[i][j] + f[i - 1][j]) % mo;
}
printf("%lld", f[n][n]);
return 0;
}
相关文章
- hdu4846 最大子正方形(dp)
- 3611: [Heoi2014]大project|树形DP|虚树
- 【BZOJ1187】[HNOI2007]神奇游乐园 插头DP
- 【BZOJ4155】[Ipsc2015]Humble Captains 最小割+DP
- 【BZOJ4543】[POI2014]Hotel加强版 长链剖分+DP
- 【BZOJ1499】[NOI2005]瑰丽华尔兹 单调队列+DP
- 【BZOJ2728】[HNOI2012]与非 并查集+数位DP
- [NOIP2016]愤怒的小鸟 D2 T3 状压DP
- L2-014. 列车调度 (DP)
- 算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索
- 登山(线性DP)
- hdu5119 Happy Matt Friends(dp)
- dp协议学习----2、SST模式下的TU的计算
- BZOJ 3329 Xorequ 数字DP+矩阵乘法
- 【hdu4734】F(x) 数位dp
- 【bzoj1231】[Usaco2008 Nov]mixup2 混乱的奶牛 状态压缩dp