BZOJ4426 :最大生产率（贪心+决策单调性DP）

题意：给出N个人，现在让你分P组，每组的工作效率是最小结束时间-最大开始时间，要求每一组的效率的正数，求最大效率和。N<1000

思路： 把包含至少一个其他的分到A组；否则到B组。

A组的要么单独分到一组，要么和它包含的某一个在一组（可以反证，假设已经分好组了，现在把不是单独分组的A加进去，如果分到不是包含关系的里面去，只会把答案变小）。

分组可以用栈进行。 而不是N^2枚举，因为多个相同的时候我们可以要保留一个作为最小的一个分到B组。

然后，现在A里面的没有包含关系了，我们可以排序，排序后一定是相邻的分到同一组，这里DP即可。

枚举单独分组的A，加上dp[][]跟新最大值即可。

原题是N<200的，我们可以用O(N^3)的DP来做。BZOJ上的N是1000的，我们需要优化，这种相邻分组的，估计要四边形不等式优化。果然是有决策单调性的，我们可以用分治来优化。  分P组，我们就P次分治。  然而我wa了N多次，因为我把不合法的部分continue了，事实上，不合法的也要更新，这样的mid才是ok的，不然单调性会出问题。

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=b;i>=a;i--)
using namespace std;
const int maxn=;
const int inf=;
pii a[maxn];int tot,cnt,ans=-inf;
int vis[maxn],dp[maxn][maxn],len[maxn],mp[maxn][maxn];
void solve(int p,int L,int R,int l,int r)
{
    if(L>R) return ;
    int Mid=(L+R)>>,res=-inf,pos=l;
    rep2(i,l,min(r,Mid-)){
        if(mp[i+][Mid]>&&dp[i][p-]+mp[i+][Mid]>res) {
            res=dp[i][p-]+mp[i+][Mid]; pos=i;
        }
    }
    dp[Mid][p]=res;
    solve(p,L,Mid-,l,pos);
    solve(p,Mid+,R,pos,r);
}
int main()
{
    int N,P;
    scanf("%d%d",&N,&P);
    rep(i,,N) scanf("%d%d",&a[i].first,&a[i].second);
    sort(a+,a+N+);
    rep(i,,N)
     rep(j,i+,N)
       if(a[i].second>=a[j].second){ vis[i]=; break;}
    rep(i,,N)
      if(vis[i]) len[++tot]=a[i].second-a[i].first;
      else a[++cnt]=a[i];
    sort(len+,len+tot+); reverse(len+,len+tot+);
    rep(i,,tot) len[i]+=len[i-];    rep(i,,cnt){
       int Mx=a[i].second,Mn=a[i].first;
       rep(j,i,cnt){
          Mx=min(Mx,a[j].second),Mn=max(Mn,a[j].first);
          mp[i][j]=Mx-Mn;
       }
    }    rep(i,,cnt) rep(j,,P) dp[i][j]=-inf;
    dp[][]=;
    rep(i,,min(P,cnt))
        solve(i,i,cnt,,cnt-);    rep(i,max(P-cnt,),tot){
        if(dp[cnt][P-i]>)
        ans=max(ans,len[i]+dp[cnt][P-i]);
    }    printf("%d\n",ans);
    return ;
}