【单调性DP】Road to Home

传送门：Codeforces721E

---

思路：

• 用$f_i$表示在前i段最多唱几首歌，$g_i$表示唱了$f_i$首歌时的最左位置；

• $$ f_i=f_j+(r-max{l,g_j+t})/p\ g_i=r-(r-max{l,g_j+t})%p $$

• 可以知道f和g是非递减的，所以用来更新i的j应该满足$x_i\leqslant j\leqslant y_i$，其中$x_i$是满足$g_{x_i}+t\leqslant l_i$的最靠右的点，$y_i$是满足$g_{y_i}+t\leqslant r_i$的最靠右的点；

• 所以可以发现相邻两个i的转移区间最多只有一个相同的点，利用这一点可以做到$O(n)$。

注意：

• 括号匹配不要写错（讲道理可以多引入几个变量）。

---

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

#define max(x,y) ((x)>(y)?(x):(y))
#define N 120000
#define INF 0x3f3f3f3f

int m,n,p,t,l[N],r[N],f[N],g[N];

int main(){
	scanf("%d%d%d%d",&m,&n,&p,&t);
	for (int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
	memset(g,INF,sizeof g); int j=0; g[0]=l[0]=r[0]=-INF;
	for (int i=1;i<=n;i++){
		f[i]=f[i-1]; g[i]=g[i-1];
		while (g[j]+t<=r[i] && j<i){
			if (f[i]<f[j]+(r[i]-max(g[j]+t,l[i]))/p || ((f[i]==f[j]+(r[i]-max(g[j]+t,l[i]))/p) && g[i]>max(g[j]+t,l[i])+(r[i]-max(g[j]+t,l[i]))/p*p)){
				f[i]=f[j]+(r[i]-max(g[j]+t,l[i]))/p;
				g[i]=max(g[j]+t,l[i])+(f[i]-f[j])*p;
			}
			j++;
		}
		j--;
	}
	printf("%d\n",f[n]);
	
	return 0;
}