[CSP-S模拟测试]:队长快跑（DP+离散化+线段树）

题目背景

传说中，在远古时代，巨龙大$Y$将$P$国的镇国之宝窃走并藏在了其巢穴中，
这吸引着整个$P$国的所有冒险家前去夺回，尤其是皇家卫士队的队长小$W$。
在$P$国量子科技实验室的帮助下，队长小$W$通过量子传输进入了巨龙大$Y$的藏宝室，并成功夺回了镇国之宝。
但此时巨龙布下的攻击性防壁启动，将小$W$困在了美杜莎的迷宫当中。

题目传送门（内部题41）

输入格式

第一行一个数$n$，表示水晶的个数。
接下来的$n$行，每行两个数$A_i,B_i$，表示第$i$个位置上的水晶的属性值。

输出格式

输出只有一行，表示在避免机关爆炸的情况下小$W$最多能够摧毁的水晶个数。

样例

样例输入：

5
2 5
3 3
7 2
8 3
4 5

样例输出：

3

数据范围与提示

对于$30\%$的数据，满足$n\leqslant 10$。
对于$60\%$的数据，满足$n\leqslant 200$。
对于另$10\%$的数据，满足$A_i,B_i\leqslant 2$。
对于$100\%$的数据，满足$n\leqslant 100,000,1\leqslant A_i,B_i\leqslant {10}^9$。

题解

爆搜有$30$分，记忆化能跑到$60$，再加上特判$A_i,B_i\leqslant 2$的点，$70$分就到手了，出题人还是蛮仁慈的。

首先，$A_i,B_i$肯定要离散化。

我们要摧毁的肯定是一个连续的区间，所以对于这段合法区间，满足$B_max

那么考虑$DP$。

设$dp[i][j]$表示处理到第$i$个水晶，已经选择的水晶中最小的$A$为$S$的最大摧毁个数。

那么考虑如何转移，分两种情况：

　　$\alpha.A_i\leqslant B_i$：$dp[i][A_i]=\max(dp[i-1][B_i+1],dp[i-1][B_i+2]...dp[i-1][MAX])+1$。

　　$\beta.A_i>B_i$：

　　　　$dp[i][A_i]=\max(dp[i-1][A_i+1],dp[i-1][A_i+2]...dp[i-1][MAX]+1$。

　　　　$dp[i][j]=dp[i-1][j]+1,j\in(B_i,A_i]$。

这时候的时间复杂度是$\Theta(n^3)$的，不过我们可以用线段树优化$DP$的第二维。

时间复杂度：$\Theta(n\log n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int n;
int a[300000],b[300000];
pair s[300000];
int tr[1000000],lz[1000000];
int ans,cnt,now;
void pushup(int x){tr[x]=max(tr[L(x)],tr[R(x)]);}
void pushdown(int x)
{if(!lz[x])return;tr[L(x)]+=lz[x];tr[R(x)]+=lz[x];lz[L(x)]+=lz[x];lz[R(x)]+=lz[x];lz[x]=0;
}
int ask(int x,int l,int r,int L,int R)
{if(R>1;return max(ask(L(x),l,mid,L,R),ask(R(x),mid+1,r,L,R));
}
void add(int x,int l,int r,int k,int w)
{if(l==r){tr[x]=max(tr[x],w);return;}pushdown(x);int mid=(l+r)>>1;if(k<=mid)add(L(x),l,mid,k,w);else add(R(x),mid+1,r,k,w);pushup(x);
}
void change(int x,int l,int r,int L,int R)
{if(R>1;change(L(x),l,mid,L,R);change(R(x),mid+1,r,L,R);pushup(x);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);s[++cnt]=make_pair(a[i],cnt);s[++cnt]=make_pair(b[i],cnt);}sort(s+1,s+cnt+1);s[0].first=-1;for(int i=1;i<=cnt;i++){if(s[i].first!=s[i-1].first)now++;if(s[i].second&1)a[(s[i].second+1)>>1]=now;else b[s[i].second>>1]=now;}for(int i=1;i<=n;i++){int maxn=((b[i]^now)?ask(1,1,now,b[i]+1,now):0)+1;ans=max(ans,maxn);if(a[i]<=b[i]+1)add(1,1,now,a[i],maxn);else{maxn=ask(1,1,now,a[i],now)+1;add(1,1,now,a[i],maxn);change(1,1,now,b[i]+1,a[i]-1);}}printf("%d",ans);return 0;
}

rp++

转载于:https://www.cnblogs.com/wzc521/p/11524121.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！