Farmer John has opened a swimming pool for his cows, figuring it will help them relax and produce more milk.
To ensure safety, he hires N cows as lifeguards, each of which has a shift that covers some contiguous interval of time during the day. For simplicity, the pool is open from time 0 until time 10^9 on a daily basis, so each shift can be described by two integers, giving the time at which a cow starts and ends her shift. For example, a lifeguard starting at time t=4 and ending at time t=7 covers three units of time (note that the endpoints are "points" in time).
Unfortunately, Farmer John hired K more lifeguards than he has the funds to support. Given that he must fire exactly K lifeguards, what is the maximum amount of time that can still be covered by the shifts of the remaining lifeguards? An interval of time is covered if at least one lifeguard is present.
Input
The first line of input contains N and K (K≤N≤100,000,1≤K≤100). Each of the next N lines describes a lifeguard in terms of two integers in the range 0…10^9, giving the starting and ending point of a lifeguard‘s shift. All such endpoints are distinct. Shifts of different lifeguards might overlap.
3 2
1 8
7 15
2 14
Output
Please write a single number, giving the maximum amount of time that can still be covered if Farmer John fires K lifeguards.
12
In this example, FJ should fire the lifeguards covering 1…8 and 7…15.
50分暴力：先将奶牛按结束时间排序
设f[i][j]表示前j头奶牛中解雇了i头奶牛且第j头奶牛没有被解雇，其余奶牛的最大覆盖为多少
转移即枚举当前这头奶牛前面连续被解雇的奶牛的数量（O(n*k*k)
#include<iostream>
#include<cstdio>
using namespace std;
int n,k,a[100001][2],f[101][100001];
void kp1(int l,int r){
int x=l,y=r,mai=a[(l+r)/2][1];
while(x<y){
while(a[x][1]<mai)x++;
while(a[y][1]>mai)y--;
if(x<=y){
swap(a[x][0],a[y][0]);
swap(a[x][1],a[y][1]);
x++;y--;
}
}if(x<r)kp1(x,r);if(l<y)kp1(l,y);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i][0],&a[i][1]);
kp1(1,n);
for(int i=1;i<=n;i++)f[0][i]=f[0][i-1]+a[i][1]-max(a[i-1][1],a[i][0]);
for(int i=1;i<=k;i++){
for(int j=i+1;j<=n;j++){
for(int k1=0;k1<=i;k1++){
f[i][j]=max(f[i][j],f[i-k1][j-k1-1]+a[j][1]-max(a[j-k1-1][1],a[j][0]));
}
}
}
int ans=f[k][n];
for(int i=1;i<=k;i++)ans=max(ans,f[k-i][n-i]);
printf("%d",ans);
return 0;
}
100分：思考如何优化转移？？？
本人对于转移优化的总结：
（1）一堆状态转移到一个状态后，考虑修改这堆状态中的个别状态，以至于可以转移到另一个状态（就是重复利用！
（2）利用数据结构
此题可以考虑（1）优化
f[i][j]->f[i+1][j];f[i][j],f[i+1][j-1]->f[i+2][j-1];f[i][j],f[i+1][j-1],f[i+2][j-2]->f[i+3][j-2]后面以此类推(每次加一个东东，就可以转移一到另一个状态了
就这样了？？？。。。。可以就好了。。
因为f[i][j]->f[k1][k2]时有两种情况(a[..][0]是左区间，a[..][1]是右区间
如果a[i][1]<=a[k1][0];f[k1][k2]=f[i][j]+a[k1][1]-a[k1][0]
否则f[k1][k2]=f[i][j]+a[k1][1]-a[i][1]
由于事先排过序所以转移来的那一堆状态中更刚好有一个分界，分界前是前者转移，分界后是后者转移
不过分界变幻莫测！！！
。
。
。
终于我想到方法了！如果一头奶牛的区间包含另一个奶牛，被包含的牛随便解雇！解雇完这些奶牛后，分界的变化呈现单调性，我们就可以用一个单调队列维护转移了（O(n*k)
#include<iostream>
#include<cstdio>
using namespace std;
int n,k,a[100001][2],f[101][100002];
int yy[100001][2],num=0;
void kp(int l,int r){
int x=l,y=r,mai=a[(l+r)/2][1],mai1=a[(l+r)/2][0];
while(x<y){
while(a[x][1]<mai||(a[x][1]==mai&&a[x][0]<mai1))x++;
while(a[y][1]>mai||(a[y][1]==mai&&a[y][0]>mai1))y--;
if(x<=y){
swap(a[x][0],a[y][0]);
swap(a[x][1],a[y][1]);
x++;y--;
}
}if(x<r)kp(x,r);if(l<y)kp(l,y);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i][0],&a[i][1]);
kp(1,n);
int u=999999999;
for(int i=n;i>=1;i--){
if(u>a[i][0]){
yy[++num][0]=a[i][0];
yy[num][1]=a[i][1];
}u=min(u,a[i][0]);
}
k=k-n+num;
k=max(k,0);
for(int i=num+1;i>=1;i--){
int zha[102],top=1,las=1,u1=0,u2=i;
zha[1]=i;
for(int j=1;j<=min(i,k+1);j++){
while(top<=las&&yy[zha[top]][1]<=yy[i-j][0])top++;
while(u2>(i-j)&&yy[u2][1]<=yy[i-j][0]){
u1=max(u1,f[i-u2][u2]);u2--;
}
f[j-1][i-j]=u1+yy[i-j][1]-yy[i-j][0];
if(top<=las)f[j-1][i-j]=max(f[j-1][i-j],f[i-zha[top]][zha[top]]+yy[i-j][1]-yy[zha[top]][1]);
zha[++las]=i-j;
while(top<las&&(f[i-zha[las]][zha[las]]-yy[zha[las]][1])>(f[i-zha[las-1]][zha[las-1]]-yy[zha[las-1]][1])){
zha[las-1]=zha[las];las--;
}
}
}
int ans=f[k][1];
for(int i=1;i<=k;i++)ans=max(ans,f[k-i][i+1]);
printf("%d",ans);
return 0;
}
