Description
给出数轴上的n个线段，保留最多k条线段，问这些被保留下来的线段的并集长度为最多为多少。
Input
第一行两个数n和k
接下来n行，每行两个数，表示一条线段的左右端点。（0<=每个数<109）
Output
一个数表示答案。
Sample Input
Sample Output
Hint
对于30%的数据，1<=n<=20
对于60%的数据，1<=n<=300
对于100%的数据，1<=n<=100000,,1<=k<=min(100,n)；
Solution
想了半天，看这个数据范围大概是nlogn可过，n*k也可过。先考虑贪心，貌似可行，但是贪心的复杂的是O(kn2logn)……手动再见还不如朴素DP。
考虑DP。朴素DP十分好想，按区间右端点排序，设f[i][j]为前i个线段选j个，其中必选i。这样易得转移方程：
f[i][j]=max(max{f[h][j-1]+r[i]-l[i]|l[i]>=r[h]},max{f[h][j-1]+r[i]-r[h]|l[i]>=r[h]})。
直观上，方程表示从前h个选j-1个开始转移，按区间是否有交划分转移。
如此转移，需要枚举当前区间，当前区间前的区间，以及线段个数，时间复杂度为O(n2k)。期望得分50分。
下面我进行了许多毫无卵用的优化：
观察前半个转移方程，需要找到前h个中最大的f[h][j-1]。显然线段树可以保存区间最大值，于是对于前半段线段树优化。这样就无需枚举h。那么如何确定h呢?考虑因为右端点满足单调性，于是进行二分。二分h的位置。复杂度O(logn)。对于后半个方程，想破脑袋也只能枚举转移，这样在期望状态下，复杂度为O(nklog2n)。两个log一个是线段树的一个是二分的。于是我们发现，我们的期望得分仍然是50分……
这是跑的最快的50分做法。差点卡常卡过70分。
下面是正解：
对于前半部分方程，需要取前i个的最大值，显然前缀最大值可做。即Max[i][j]=max(Max[i-1][j],frog[i][j])这样，对于前半部分的转移，转移时间从O(logn)降低到了O(1)。可是这样期望还是50分啊。考虑最大h的位置。由于满足右端点递增，如果在排序是将左端点为第二关键字升序排序，那么显然h是递增的。因为h代表的是右端点小于等于l[i]的右端点区间最大的编号。由于r[i]递增，l[i]升序，所以l[i]递增。(对于相互包含的区间，显然大区间优于小区间，需要去重）这样只需要不断++h，判断h是否合法即可。这样，决策时间也降到了O(1)。下面考虑对于后半部分方程的转移。由于r[i]、l[i]递增，所以满足第二部分方程的h是递增的。如此可以进行单调队列优化。对于合法的但是小的f，会被新进队列的元素直接覆盖。不合法的会从队首弹出。如此，整个转移的复杂度被降到了O(1)。所以本题的复杂度为Θ(nk+n+nlogn)，其中nk为DP，n为单调队列总维护次数，nlogn为排序复杂的。即O(nk)。这样复杂度就合法通过了本题。
Code
#include<cstdio>
#include<algorithm>
#define maxn 100010 inline void qr(int &x) {
char ch=getchar();bool f=false;
while(ch>''||ch<'') {
if(ch=='-') f=true;
ch=getchar();
}
while(ch>=''&&ch<='') x=(x<<)+(x<<)+(ch^),ch=getchar();
if(f) x=-x;
} inline int max(const int &a,const int &b) {if(a>b)return a;else return b;}
inline int min(const int &a,const int &b) {if(a<b)return a;else return b;}
inline int abs(const int &x) {if(x>=) return x;else return -x;} inline void swap(int &a,int &b) {
int temp=a;a=b;b=temp;
} int n,k,ans;
struct M {
int l,r;
};
M MU[maxn];
int frog[maxn][];
inline bool cmp(const M &a,const M &b) {
if(a.r!=b.r) return a.r<b.r;
return a.l<b.l;
} int main() {
freopen("cover10.in","r",stdin);
freopen("ans.out","w",stdout);
qr(n);qr(k);
for(int i=;i<=n;++i) {
qr(MU[i].l);qr(MU[i].r);
}
std::sort(MU+,MU++n,cmp);
for(int i=;i<=n;++i) {
frog[i][]=MU[i].r-MU[i].l;
for(int j=k;j>;--j) {
for(int h=;h<i;++h) {
if(MU[h].r<=MU[i].l) frog[i][j]=max(frog[i][j],frog[h][j-]+MU[i].r-MU[i].l);
else frog[i][j]=max(frog[i][j],frog[h][j-]+MU[i].r-MU[h].r);
}
}
ans=max(ans,frog[i][k]);
}
printf("%d\n",ans);
return ;
}
50分无优化
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
ld eps=1e-;
ll pp=;
ll mo(ll a,ll pp){if(a>= && a<pp)return a;a%=pp;if(a<)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=;for(;b;b>>=,a=mo(a*a,pp))if(b&)ans=mo(ans*a,pp);return ans;}
ll read(){
ll ans=;
char last=' ',ch=getchar();
while(ch<'' || ch>'')last=ch,ch=getchar();
while(ch>='' && ch<='')ans=ans*+ch-'',ch=getchar();
if(last=='-')ans=-ans;
return ans;
}
//head
#define N 110000
ll f[][N];
pr a[N];
int n,k,nn,q[N];
ll b[N],c[N];
int main(){
freopen("cover.in","r",stdin);
freopen("cover.out","w",stdout);
n=read();k=read();
rep(i,,n)a[i].first=read(),a[i].second=read();
sort(a+,a+n+);
nn=;
rep(i,,n)
if(a[nn].second<a[i].second)a[++nn]=a[i];
n=nn;k=min(k,n);
rep(i,,)
rep(j,,n)f[i][j]=-;
f[][]=;
int ans=;
rep(i,,k-){
b[]=f[][];
rep(j,,n)b[j]=max(f[][j],b[j-]);
rep(j,,n)c[j]=f[][j]-a[j].second;
int t=,w=,z=;
rep(j,i+,n){
while(a[z+].second<=a[j].first)++z;
while(t<=w && c[j-]>=c[q[w]])--w;
q[++w]=j-;
while(t<=w && q[t]<=z)++t;
f[][j]=b[z]+a[j].second-a[j].first;
if(t<=w)f[][j]=max(f[][j],c[q[t]]+a[j].second);
ans=max((ll)ans,f[][j]);
}
rep(j,,n)f[][j]=f[][j],f[][j]=-;
} printf("%d\n",ans);
return ;
}
Summary
1、在需要前i个元素中最大值且i转移单调时，考虑前缀最大值而不是线段树。这样复杂度可以下降为O(1)。其实我就是数据结构学傻了
2、转移区间满足单调性时，考虑单调队列优化。需要注意的是，单调队列中单调的是元素下标而不是DP值。这不是废话吗
3、神仙题优化时可以画图考虑转移位置，从而发现性质。