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

点击量：225

    这个题的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;
}