Mail.Ru Cup 2018 Round 2

E.Segments on the Line

$\mathtt{Difficulty}$=$\mathtt{2500}$
不难想到二分答案 $x$，验证是否有 $k$ 个及以上个的值小于 $x$。
对于这个问题，我们考虑 $\texttt{dp}$。
不妨设 $dp_{i,j}$ 表示前 $i$ 个点已经选择了 $j$ 条线段。
转移考虑要么直接与上一个段重叠，要么不重叠（忽略包含的情况，因为这只意味着可以选择少于 $m$ 段）。
重叠的情况下，选择上一个段显然是最优的。
不重叠的情况下，直接找包含这个点的左端点最左显然是最优的。

#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
using namespace std;
int N,M,S,K,A[10001],L[10001],R[10001],Dp[5001][5001];
inline bool Check(int X)
{
	register int i,j;memset(Dp,0,sizeof(Dp));
	for(i=1;i<=N;i++)
	{
		register int Last(i+1),Sum(0);
		for(j=1;j<=M;j++)if(L[j]<=i&&R[j]>=i)Last=min(Last,L[j]);
		for(j=Last;j<=i;j++)Sum+=(A[j]<=X);
		for(j=1;j<=S;j++)Dp[i][j]=max(Dp[i-1][j],Dp[Last-1][j-1]+Sum);
	}
	return Dp[N][S]>=K;
}
int main(void)
{
	BetterIO;
	register int i;cin>>N>>M>>S>>K;
	for(i=1;i<=N;i++)cin>>A[i];
	for(i=1;i<=M;i++)cin>>L[i]>>R[i];
	register int Left(1),Right(1000000000),Ans=-1;
	while(Left<=Right)
	{
		register int Middle=Left+Right>>1;
		if(Check(Middle))Ans=Middle,Right=Middle-1;
		else Left=Middle+1;
	}
	cout<<Ans<<endl;
	return 0;
}