对于每个点向后一个点连流量为k费用为0的边
对每一区间连l到r流量为1费用为r-l的边
然后最小费用最大流，输出取反
一开始写的r-l+1错了半天。。。
By：大奕哥
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=10000005,inf=1e9; 4 int head[N],d[N],f[N],l[N],r[N],a[N],s=1e9,t,n,k,cnt=-1,cost; 5 bool v[N]; 6 struct node{ 7 int to,nex,f,w,c; 8 }e[1000005]; 9 void add(int x,int y,int w,int c) 10 { 11 e[++cnt].to=y;e[cnt].w=w;e[cnt].f=x;e[cnt].c=c;e[cnt].nex=head[x];head[x]=cnt; 12 e[++cnt].to=x;e[cnt].w=0;e[cnt].f=y;e[cnt].c=-c;e[cnt].nex=head[y];head[y]=cnt; 13 } 14 queue<int>q; 15 bool spfa() 16 { 17 memset(f,-1,sizeof(f)); 18 memset(d,0x3f,sizeof(d)); 19 memset(v,0,sizeof(v)); 20 d[s]=0;v[s]=1;q.push(s); 21 while(!q.empty()) 22 { 23 int x=q.front();q.pop();v[x]=0; 24 for(int i=head[x];i!=-1;i=e[i].nex) 25 { 26 int y=e[i].to; 27 if(d[y]<=d[x]+e[i].c||!e[i].w)continue; 28 d[y]=d[x]+e[i].c;f[y]=i; 29 if(!v[y])q.push(y),v[y]=1; 30 } 31 } 32 if(d[t]>1e9)return 0; 33 int flow=inf; 34 for(int i=f[t];i!=-1;i=f[e[i].f]) 35 flow=min(flow,e[i].w); 36 for(int i=f[t];i!=-1;i=f[e[i].f]) 37 e[i].w-=flow,e[i^1].w+=flow,cost+=e[i].c*flow; 38 return 1; 39 } 40 int main() 41 { 42 scanf("%d%d",&n,&k);int num=0; 43 memset(head,-1,sizeof(head)); 44 for(int i=1;i<=n;++i) 45 { 46 scanf("%d%d",&l[i],&r[i]); 47 a[++num]=l[i];a[++num]=r[i]; 48 } 49 sort(a+1,a+1+num); 50 num=unique(a+1,a+1+num)-a-1; 51 for(int i=1;i<=n;++i) 52 { 53 int x=r[i]-l[i]; 54 l[i]=lower_bound(a+1,a+1+num,l[i])-a; 55 r[i]=lower_bound(a+1,a+1+num,r[i])-a; 56 add(l[i],r[i],1,-x); 57 } 58 for(int i=1;i<num;++i) 59 add(i,i+1,k,0);t=num+1; 60 add(num,t,k,0); 61 add(0,1,k,0);s=0; 62 while(spfa()); 63 printf("%d ",-cost); 64 return 0; 65 }