【神仙DP】【单调队列】【模拟题】区间覆盖
Description
给出数轴上的n个线段，保留最多k条线段，问这些被保留下来的线段的并集长度为最多为多少。
Input
第一行两个数n和k
接下来n行，每行两个数，表示一条线段的左右端点。（0<=每个数<109）
Output
一个数表示答案。
Sample Input
3 2 1 8 7 15 2 14
Sample Output
12
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>'9'||ch<'0') { if(ch=='-') f=true; ch=getchar(); } while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),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>=0) 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][110]; 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=1;i<=n;++i) { qr(MU[i].l);qr(MU[i].r); } std::sort(MU+1,MU+1+n,cmp); for(int i=1;i<=n;++i) { frog[i][1]=MU[i].r-MU[i].l; for(int j=k;j>1;--j) { for(int h=0;h<i;++h) { if(MU[h].r<=MU[i].l) frog[i][j]=max(frog[i][j],frog[h][j-1]+MU[i].r-MU[i].l); else frog[i][j]=max(frog[i][j],frog[h][j-1]+MU[i].r-MU[h].r); } } ans=max(ans,frog[i][k]); } printf("%d\n",ans); return 0; }
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(-1); #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-9; ll pp=1000000007; ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;} ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} ll read(){ ll ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; return ans; } //head #define N 110000 ll f[2][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,1,n)a[i].first=read(),a[i].second=read(); sort(a+1,a+n+1); nn=1; rep(i,2,n) if(a[nn].second<a[i].second)a[++nn]=a[i]; n=nn;k=min(k,n); rep(i,0,1) rep(j,0,n)f[i][j]=-1000000; f[0][0]=0; int ans=0; rep(i,0,k-1){ b[0]=f[0][0]; rep(j,1,n)b[j]=max(f[0][j],b[j-1]); rep(j,0,n)c[j]=f[0][j]-a[j].second; int t=1,w=0,z=0; rep(j,i+1,n){ while(a[z+1].second<=a[j].first)++z; while(t<=w && c[j-1]>=c[q[w]])--w; q[++w]=j-1; while(t<=w && q[t]<=z)++t; f[1][j]=b[z]+a[j].second-a[j].first; if(t<=w)f[1][j]=max(f[1][j],c[q[t]]+a[j].second); ans=max((ll)ans,f[1][j]); } rep(j,0,n)f[0][j]=f[1][j],f[1][j]=-1000000; } printf("%d\n",ans); return 0; }
Summary
1、在需要前i个元素中最大值且i转移单调时，考虑前缀最大值而不是线段树。这样复杂度可以下降为O(1)。其实我就是数据结构学傻了
2、转移区间满足单调性时，考虑单调队列优化。需要注意的是，单调队列中单调的是元素下标而不是DP值。这不是废话吗
3、神仙题优化时可以画图考虑转移位置，从而发现性质。