CodeForces-102D（线性dp + 前缀和+二分）

题目链接：Problem - 102D - Codeforces
题意： 小明要通过坐车从家里到学校，家里的站点为0，学校的站点为n，然后给出m辆车的起点和终点，小明可以从起点到终点之间(包括起点不包括终点)上车，但是一旦上车，到了终点才能下车，求小明从家里到学校一共有多少种方法，（不同车也算不同方法）
思路：
题目求的是到达n点有多少种方法，很容易可以想到这道题用dp来写(因为很典型)。但是如果用dp[i]表示到第几个点时候的方法数的话，数据存不下1e9必然不可行,然后我们看到车的数量为1e5，也就是说一共有1e5个终点。所以我们可以将终点离散化(这里看不懂，也没关系，其实就是排个序)，将终点排序，所以dp[i]的含义就变成为到第i个终点时候的方法数。
确定了dp的含义，接下来找状态转移方程，因为小明从起点到终点之间(包括起点不包括终点)可以上车，所以可以得出dp[i] = dp[起点] +dp[起点+

CodeForces-102D（线性dp + 前缀和+二分）最先出现在Python成神之路。