很巧妙的建图啊...刚了$1h$也没想出来，最后看的题解

发现这道题并不类似于我们平时做的网络流题，它是在序列上的，且很难建出来二分图的形。

那就让它在序列上待着吧= =

对于一个区间，左端点向右端点连边，流量为$1$，费用为区间长度

对于一个位置$i$，向$i+1$连边，流量为$K$，费用为$0$

为什么要这么建图呢？

假设有$1$流量流到了位置$i$，有两种情况

1.选择一个从i开始的区间$[i,r]$，这点流量流到了$r$位置。而在$(i,r)$内，这点流量不能用于其它区间，达到了限制区间个数的目的，然后我们获得了$r-i$点收益

2.不选任何区间，流量流到了$i+1$位置，为后面的区间提供流量

然后跑最大费用最大流就行了

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define N1 2005 5 #define M1 100100 6 #define ll long long 7 #define dd double 8 #define inf 0x3f3f3f3f 9 using namespace std;10 11 int gint()12 {13     int ret=0,fh=1;char c=getchar();14     while(c<'0'||c>'9'){
   if(c=='-')fh=-1;c=getchar();}15     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}16     return ret*fh;17 }18 int n,K,S,T;19 struct Edge{20 int head[N1],to[M1<<1],nxt[M1<<1],flow[M1<<1],dis[M1<<1],cte;21 void ae(int u,int v,int F,int D)22 {23     cte++; to[cte]=v; flow[cte]=F; dis[cte]=D;24     nxt[cte]=head[u]; head[u]=cte;25 }26 }e;27 28 int que[M1<<1],hd,tl,dis[N1],id[N1],flow[N1],use[N1];29 int spfa()30 {31     int x,j,v;32     memset(dis,-1,sizeof(dis)); memset(flow,0,sizeof(flow)); memset(use,0,sizeof(use));33     hd=1,tl=0; que[++tl]=S; dis[S]=0; use[S]=1; flow[S]=inf;34     while(hd<=tl)35     {36         x=que[hd++]; 37         for(j=e.head[x];j;j=e.nxt[j])38         {39             v=e.to[j]; 40             if( e.flow[j]>0 && dis[v]
        
         r[i]) swap(l[i],r[i]); 74         t[++cnt]=l[i]; t[++cnt]=r[i]; len[i]=r[i]-l[i]+1;75     } 76     sort(t+1,t+cnt+1); cnt=unique(t+1,t+cnt+1)-(t+1);77     for(i=1;i<=n;i++) l[i]=lower_bound(t+1,t+cnt+1,l[i])-t;78     for(i=1;i<=n;i++) r[i]=lower_bound(t+1,t+cnt+1,r[i])-t;79     S=0; T=cnt+1;80     for(i=1;i<=n;i++) e.ae(l[i],r[i]+1,1,len[i]), e.ae(r[i]+1,l[i],0,-len[i]);81     for(i=1;i<=cnt;i++) e.ae(i,i+1,K,0), e.ae(i+1,i,0,0); e.ae(S,1,K,0); e.ae(1,S,0,0);82     printf("%d\n",EK()); 83     return 0;84 }