关于P6007

回复帖子

@Longest_Journey  2021-04-08 00:07 回复

这道题目我的做法如下:

  1. 将 $(x_1,y_1),(x_2,y_2)$放在一个数组内记录原下标,然后进行离散化

  2. 进行DP

我的代码:(只过了样例)

#include<cstdio>
#include<iomanip>
#include<algorithm>
#define lowbit(i) i&(-i)
#define p1 (p<<1)
using namespace std;
const int N=2e5+50;
struct point{
    int x,y,px,py,idx;
}a[N];
int f[N],c[N],pos[N];//pos[i]表示离散化后i号节点所对应的原下标 
int n,p;
inline int Max(int a,int b){return a>b?a:b;}
bool cmp1(point p,point q){return p.x<q.x;}
bool cmp2(point p,point q){return p.y<q.y;}

inline void Insert(int x,int y){for(;x<=n;x+=lowbit(x)) c[x]=Max(c[x],y);}
inline int Query(int x)
{
    int ans=0;
    for(;x>0;x-=lowbit(x)) ans=Max(ans,c[x]);
    return ans;
}

void Work()//离散化,将y和x分开 
{
    sort(a+1,a+1+p1,cmp2);
    a[0].py=1;
    for(int i=1;i<=p1;i++){
        if(a[i].y==a[i-1].y) a[i].py=a[i-1].py;
        else a[i].py=a[i-1].py+1;
    }
    sort(a+1,a+1+p1,cmp1);
    a[0].px=1;
    for(int i=1;i<=p1;i++){
        if(a[i].x==a[i-1].x) a[i].px=a[i-1].px;
        else a[i].px=a[i-1].px+1;
        pos[a[i].idx]=i;
    }   
}
int main()
{
    scanf("%d%d",&n,&p);
    for(int i=1;i<=p;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
        scanf("%d%d",&a[i+p].x,&a[i+p].y);
        a[i].idx=i,a[i+p].idx=i+p;//将i号跳板的终点存在i+p处 
    }
    Work();

    for(int i=1;i<=p1;i++){
        if(a[i].idx>p) continue;
        f[i]=Query(a[i].py)-a[i].px-a[i].py+a[pos[a[i].idx+p]].px+a[pos[a[i].idx+p]].py;
        Insert(a[i].py,f[i]);
    }
    int maxn=0;
    for(int i=1;i<=p1;i++) maxn=Max(maxn,f[i]);
    printf("%d\n",(n<<1)-maxn);
    return 0;
}

求助各位大佬

@fffngzzh 2021-04-08 13:51 回复 举报

你看Insert函数里

$x<=n$

你的数组c只开了 $2×10^{5}+50$

数据范围 $1 \leq N \leq 10^9$

所以一旦 $N$ 比较大就RE

@fffngzzh 2021-04-08 18:19 回复 举报
inline void Insert(int x,int y){
    for(;x<=n;x+=lowbit(x))             c[x]=Max(c[x],y);
}

注意你的 $n$ 在运行这个函数时毫无变化

@fffngzzh 2021-04-08 18:29 回复 举报
1000000000 20
2 3 1 4
3 4 2 5
4 5 3 6
5 6 4 7
6 7 5 8
7 8 6 9
8 9 7 10
9 10 8 11
10 11 9 12
11 12 10 13
12 13 11 14
13 14 12 15
14 15 13 16
15 16 14 17
16 17 15 18
17 18 16 19
18 19 17 20
19 20 18 21
20 21 19 22
21 22 20 23

你看一下这个输入样例

你的代码会在 $x=524288$ 时RE

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。