【DP】【前缀和】[2018.10雅礼] 折射 题解

 

    这个题的50分做法比100分做法要麻烦……但是100分有点反人类了

 

题目描述

小\(\mathrm{Y}\)十分喜爱光学相关的问题,一天他正在研究折射.

 

他在平面上放置了\(n\)个折射装置,希望利用这些装置画出美丽的折线.

 

折线将从某个装置出发,并且在经过一处装置时可以转向,若经过的装置坐标依次为\((x_1, y_1),(x_2,y_2),\dots (x_k, y_k)\), 则必须满足:

  • \(\forall j\in (1,k],y_j<y_{j-1}\)
  • \(\forall j\in (2,k],x_{j-2}<x_j<x_{j-1}\ \mathrm{or}\ x_{j-1}<x_j<x_{j-2}\)

现在他希望你能告诉他,一共有多少种不同的光线能被他画出来,两种光线不同当且仅当经过的折射装置的集合不同.你只需要告诉他答案对\(10^9+7\)取模后的结果.

 

输入输出格式

输入格式:

第一行一个正整数\(n\),表示折射装置的数量.

 

接下来\(n\)行,每行两个整数\(x_i,y_i\)表示折射装置的坐标.

 

输出格式:

输出一行一个整数,表示答案对\(10^9+7\)取模后的结果.

 

输入输出样例

输入样例#1:

4
2 2
3 1
1 4
4 3
输出样例#1:

14

说明

对于\(10\%\)的数据:\(n\le 700,1\le x_i,y_i\le n\)

对于\(20\%\)的数据:\(n\le 1000,1\le x_i, y_i\le n\)

对于\(50\%\)的数据:\(n\le 4000,|x_i|,|y_i|\le 10^9\)

对于\(100\%\)的数据:\(n\le 6000,|x_i|,|y_i|\le 10^9\)

所有数据满足\(\forall i\not=j,x_i\not=x_j\ \mathrm{and}\ y_i\not=y_j\).

 

题解:

20分小常数做法:

    把整个坐标系逆时针旋转90°,把点按纵坐标\(y\)降序排序,可以发现满足条件的折线横坐标在前两个点之间\((x_i\in (\min(x_{k-1},x_{k-2}),\max(x_{k-1},x_{k-2})))\),此时是可以用数组表示的。令\(f_{i,j}\)表示折线的结尾为第\(i\)个点(按纵坐标降序排序后),折线的倒数第二个为第\(j\)个点。这样的转移如果不直观,可以先离散化,然后把第二维改成倒数第二个点的横坐标,这样方便判断转移的合法性,让状态转移方程的长度短一点,注意初始化时\(f_{i,0}\)和\(f_{i,n+1}\)为\(1\)。

 

    枚举求\(\forall j<i,f_{i,j}=\begin{cases}\sum_{k=0}^{x_i-1} f_{j,k} & x_j>x_i \\ \sum_{k=x_i+1}^{n+1} f_{j,k} & x_j<x_i \end{cases}\)

 

    最后统计答案也要枚举所有的\(f_{i,j}\)。由于每个点初始化赋了2个\(1\),但是答案只统计一次,所以最终答案要减去\(n\)。

 

50分爆空间做法:

    针对上述转移方程,\(\forall j<i,f_{i,j}=\begin{cases}\sum_{k=0}^{x_i-1} f_{j,k} & x_j>x_i \\ \sum_{k=x_i+1}^{n+1} f_{j,k} & _j<x_i \end{cases}\)中,形如\(\sum_{k=0}^{x_i-1} f_{j,k}\)这样的求和,是可以在\(O(n^2)\)的DP过程中顺便处理出来并且不增加时间复杂度的。但是这种拿空间换时间的行为,让空间变得大了许多。空间复杂度是带大常数的\(\Omega(n^2)\),128Mb的空间只能支持到\(n=4000\)。

 

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
struct pnt
{
    int x,y;
    friend bool operator <(pnt a,pnt b)
    {
        return a.y>b.y;
    }
}a[6666];
bool cmp(pnt a,pnt b)
{
    return a.x<b.x;
}
int f[4001];
int sum[4001][4001],mus[4001][4001];
int x[6001];
int main()
{
    int n;
    scanf("%d",&n);
    if(n>4000)
    {
    	printf("0");
    	return 0;
	}
    for(int i=1;i<=n;++i)
        scanf("%d%d",&a[i].x,&a[i].y);
    std::sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;++i)
        a[i].x=i;
    std::sort(a+1,a+1+n);
    for(int i=1;i<=n;++i)
    {
        a[i].y=i;
        x[a[i].x]=i;
    }
    long long ans=0;
    for(int i=1;i<=n;++i)
    {
    	memset(f,0,sizeof(f));
    	f[0]=1;
    	f[n+1]=1;
        for(int j=1;j<i;++j)
            if(a[i].x<a[j].x)//要找更小的
                f[a[j].x]=(f[a[j].x]+sum[j][a[i].x-1])%1000000007;
            else
                f[a[j].x]=(f[a[j].x]+mus[j][a[i].x+1])%1000000007;
        sum[i][0]=f[0];
        for(int j=1;j<=n+1;++j)
            sum[i][j]=(sum[i][j-1]+f[j])%1000000007;
        for(int j=n+1;j>=0;--j)
            mus[i][j]=(mus[i][j+1]+f[j])%1000000007;
        for(int j=0;j<=n+1;++j)
        	ans=(ans+f[j])%1000000007;
    }
    printf("%lld\n",ans-n);
    return 0;
}

 

100分玄学转移:

    正常的DP过程是\(y\)递减,按光的顺序转移。但是实际上,直接按\(x\)升序转移,是可以达到更优的,甚至不用离散化。而且这个转移真的很神很神。

 

    把所有点按\(x\)升序排序,按顺序每次加入一个,那么根据限制2,这个点在当前存在的光线中,要么是第一个点(发射点),要么是第二个点。我们基于这个进行转移,这时,一个新的点\((x_i,y_i)\)被加入,就可以给左边(\(x_j<x_i,y_j>y_i\))的点增加方案。增加的方案数是以\(i\)为发射点,向左发射光线到所有\(k\)点(\(x_j<x_k<x_i\))的方案数,这个也可以用前缀和处理出来,但是还有一种更神奇的转移方式。

 

    首先是正常的前缀和。因为我们要求\(x_k>x_j\),所以在枚举从\(i-1\)到\(j\)的过程中,用临时的\(sum_j\)表示\([j,i)\)区间中,符合上述条件的方案数,就避免了上一行重新枚举\(k\)点的复杂度。实际上,我们dp转移的就是\(i\)点能向左发射的光线数,而此时当\(k\)枚举到一个位置时,\(i\)的转移也只枚举到了这里,那么此时直接加上\(i\)向左的方案数就可以了,不用额外的前缀和数组。

 

    最后要注意的是\(ans=(ans+f_{i,0}+f_{i_1})\% p\)时,\(ans,f_{i,0},f_{i,1}\)的数量级都是\(10^9\),加起来有爆int的几率,事实上数据点中全部都会爆,注意分开取模。

 

Code:

#include<cstdio>
#include<algorithm>
struct pnt
{
    int x,y;
    friend bool operator <(pnt a,pnt b)
    {
        return a.x<b.x;
    }
}a[6005];
int f[6005][2];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&a[i].x,&a[i].y);
    std::sort(a+1,a+1+n);
    for(int i=1;i<=n;++i)
    {
        f[i][0]=1;
        f[i][1]=1;
        for(int j=i-1;j;--j)
            if(a[j].y>a[i].y)
                f[j][0]=(f[j][0]+f[i][1])%1000000007;
            else
                f[i][1]=(f[i][1]+f[j][0])%1000000007;
    }
    int ans=0;
    for(int i=1;i<=n;++i)
        ans=((ans+f[i][0])%1000000007+f[i][1]-1)%1000000007;
    printf("%d\n",ans);
    return 0;
}