题解

样例分析

第一组样例：
[1       5]
[1     4]               10
          [5       9]
输出：选[1,5]，摸鱼时间为5（6、7、8、9、10）
第二组样例：
[1   3]
[1 2] 
      [3         7]
      [3     6]
        [4              11]    14
              [6 7]
                  [7   9]
输出：选[1 2]、[3 7]，摸鱼时间为7(8、9、10、11、12、13、14)

思路

$n$ 个时间段 $[l_i,r_i]$，按照开始时间从小到大排序。

定义$dp[i]$，表示以第 $i$ 个线段结尾的摸鱼时间最大值

需要考虑 $dp$ 的起始状态、状态转移方程、输出的最终结果。

起始状态

可能有 $l_i$ 相同的时间段，需要把和 $l_1$ 相同的 $l_i$ 这个时间段全部赋初值。

int id=1;
while(id<=n && a[id].l==a[1].l){
	dp[id]=a[1].l-1;
	id++;
}

状态转移方程

假设 第 $i$ 个时间段是由第 $j$ 个时间段转移来的$( i 到 j 之间的时间段为 k )$。需要符合的条件：

• $l_i$ >$r_j$
• $max(l_k)$ $\leq$ $r_j$

for(int i=id;i<=n;i++)
{
	for(int j=1;j<i;j++)  //i是由j转移来的，找到一个合适的j 
	{
		int mx=0;
		for(int k=j+1;k<i;k++)  //j~i之间的线段 
		{
			 if(a[k].l!=a[i].l)
			 	mx=max(mx,a[k].l);
		}
		if(mx<=a[j].r&&a[i].l>a[j].r)
			dp[i]=max(dp[i],dp[j]+a[i].l-a[j].r-1);
	}
}

输出最终结果

考虑哪一个时间段可以作为结尾？
假设结尾的时间段为 $i$， 需要满足的条件为：

• $r_i \geq l_n$

int ans=0;
for(int i=1;i<=n;i++){
    if(a[i].r>=a[n].l)
	ans=max(ans,dp[i]+T-a[i].r);	
}
cout<<ans;

优化

上述时间复杂度 $O(n^3)$
寻找合适的 $j$ 线段可以优化：

for(int i=id; i<=n; i++)
{
	int ma=0;
	for(int j=i-1; j>=1; j--)
	{
		if(ma<=a[j].r&&a[i].l>a[j].r) 
			dp[i]=max(dp[j]+a[i].l-a[j].r-1,dp[i]);
		if(a[j].l!=a[i].l) ma=max(ma,a[j].l);
	}
}

复杂度 $O(n^2)$