题目链接

题意分析

计数问题跑DP 这是常识原谅我第一时间没有想出来

我们用dp[i]表示搭乘第i辆车下车的方案数

最终的答案 就是把所有终点站ti=n的车下车的方案数累加

现在考虑怎么转移

我们先把所有车按照终点站排序

对于第i辆车 查找哪些车会停在[si,ti-1] 将这些车的方案累加到dp[i]上

用于终点站是单调的 所以我们可以使用二分确定

由于有贡献的车必然是一段连续的区间 所以我们通过前缀和优化累加

CODE:

#include
#define N 300080
#define mod 1000000007
using namespace std;
int n,m;
struct Node
{
	int s,t;
	friend bool operator <(const Node &A,const Node &B)
	{return A.t>1;
			if(e[mid].t>=e[i].s) {tmp1=mid;ri=mid-1;}
			else le=mid+1;
		}
		le=1;ri=i-1;
		while(le<=ri)
		{
			int mid=(le+ri)>>1;
			if(e[mid].t