题解 P3562 【[POI2013]LAS-Laser】

kczno1 · 2017-02-26 08:34:11 · 题解

根据角度离散线段端点。

而且射线必定经过某个线段端点，否则可以移动，且不会更差。

变成一些区间，选择一些点，使得涉及的区间最多，且没有区间被重复涉及。

也就是没有两个点在同一区间。

那么一个点i选择后，剩下的1->i的选择一定是一段前缀。而且是从i涉及的区间的最左端点left[i]的左边开始的。

f[i][j]表示前i个点选择了j个最多涉及的区间。

f[i][j]=max(f[i-1][j],f[left[i]-1][j-1]+num[i])

空间5*10^7个int是开不下的。

所以枚举j，再枚举i，之后可以在数组中删掉一维。

(一开始少打了个0，结果95)

#include<bits/stdc++.h>
using std::sort; 

void chmax(int &x,int y) { if(x<y)x=y; }
void chmin(int &x,int y) { if(x>y)x=y; }
#define ll long long
#define B 800005
#define N 2000010
struct point 
{
    int x,y;
    friend ll operator *(const point &x,const point &y)
    {
      return (ll)x.x*y.y-(ll)x.y*y.x;
    }
}p0[N],*p[N];
int w[N];//离散后的位置 
int t1;
void ins(point *i)
{
    scanf("%d%d",&i->x,&i->y);
    p[++t1]=i; 
}

bool xiao(point *x,point *y)//y在x逆时针旋转方向 也就是x叉积y>0 
{
    return (*x)*(*y)>0;
}
int top;
int left[N],num[N],f[N];

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    int k,n,i;scanf("%d%d",&k,&n);
    for (i=1;i<=n;++i)
    {
        ins(p0+i);ins(p0+i+B);
    }
    sort(p+1,p+t1+1,xiao);
    top=1;
    int j=p[1]-p0;
    point now=p0[j];
    w[j]=1;
    for (int i=2;i<=t1;++i) 
    {
        int j=p[i]-p0;
      if (p0[j]*now) {now=p0[j];++top;}
      w[j]=top;
    }

    int x,y;
    for (i=1;i<=top;++i) left[i]=N;
    for (i=1;i<=n;++i)
    {
      if (w[i]>w[B+i]) {x=w[B+i];y=w[i];}
      else {x=w[i];y=w[B+i];} 
      chmin(left[y],x);//chmin(left[x..y],x) 先更新最右的 最后从右往左更新一遍
      ++num[x];--num[y+1];//[x,y]+1,差分 
    }
    for (i=1;i<=top;++i) num[i]+=num[i-1];
    for (i=top-1;i>=1;--i)  chmin(left[i],left[i+1]);

    while (k--)
    {
        for (i=top;i;--i) chmax(f[i],f[left[i]-1]+num[i]);//逆着来,此时f[left[i]-1]还是上一次的 
        for (i=1;i<=top;++i) chmax(f[i],f[i-1]);//顺着来，这样f[i-1]就是这一次的 
    }
    printf("%d",f[top]);
}