雅礼集训 Day1 T2 折射

折射

题目描述

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

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

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

(forall jin (1,k],y_j<y_{j-1})
(forall jin (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)取模后的结果.

说明

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

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

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

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

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

最后五分钟发现题目看错了emm，爆0嘞

后来发现STD的做法简直玄妙至极

有很多空间(O(n^2))，时间(O(n^2))的50pts做法，不多提了

正解(dp_{i,0/1})代表按(x)排序以(i)为入射点的光线，像左下方0/右下方1入射，注意这里前(i)并不是状态，因为后面可以更改这个(dp_i)状态，按(x)排序只是为了方便处理

转移呢?

(forall y_j<y_i,dp_{i,0} leftarrow dp_{j,1})

(forall y_j>y_i,dp_{j,1} leftarrow dp_{k,0}|y_k<y_i and x_k>x_j)

这里直接借用题解里面说的了

写法也很妙

总结：对于给了一些单调限制条件的(dp)，不妨根据限制条件设计方程

Code:

#include <cstdio>
#include <algorithm>
const int N=6010;
const int mod=1e9+7;
struct node
{
    int x,y;
    bool friend operator <(node n1,node n2){return n1.x<n2.x;}
}dx[N];
int n,dp[N][2],ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&dx[i].x,&dx[i].y);
    std::sort(dx+1,dx+1+n);
    dp[1][0]=dp[1][1]=1;
    for(int i=2;i<=n;i++)
    {
        dp[i][0]=dp[i][1]=1;
        for(int j=i-1;j;j--)
            if(dx[j].y>dx[i].y)
                (dp[j][1]+=dp[i][0])%=mod;
            else
                (dp[i][0]+=dp[j][1])%=mod;
    }
    for(int i=1;i<=n;i++) (ans+=dp[i][0])%=mod,(ans+=dp[i][1]-1)%=mod;
    printf("%d
",ans);
    return 0;
}

2018.10.1