线段并交问题——抓住包含关系/转移贡献用端点加减表示：0922T3

http://cplusoj /d/senior/p/SS230922C

首先有个贪心，按长度从大往小选，是错的

然后有个dp，按左端点排完后选连续段，也是错的

但把上面两个结合起来，还是错的

然后此时错的有个共性，就是存在区间包含关系

然后我们把区间包含关系去掉，另外统计贡献，那样是对的

只不过超时而已

然后发现dp转移的贡献函数可以直接拿端点值之差来表示

然后就可以前缀和了

#include<bits/stdc++.h> using namespace std; #define int long long inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'|| ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;} #define Z(x) (x)*(x) #define pb push_back //mt19937 rand(time(0)); //mt19937_64 rand(time(0)); //srand(time(0)); #define N 5010 //#define M //#define mo struct node { int l, r, len; }a[N]; int n, m, i, j, k, T, sum; int ans, l, r, s[N][N], f[N][N], b[N], p[N], g[N][N]; int mx; void sol1() { l=0; r=1e9; sort(a+1, a+n+1, [] (node x, node y) { return x.len>y.len; }); for(i=1; i<m; ++i) sum+=a[i].len; for(i=m; i<=n; ++i) l=max(l, a[i].l), r=min(r, a[i].r); sum+=max(0ll, r-l); ans=max(ans, sum); } signed main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); freopen("se.in", "r", stdin); freopen("se.out", "w", stdout); // T=read(); // while(T--) { // // } n=read(); m=read(); for(i=1; i<=n; ++i) { a[i].l=read(); a[i].r=read(); a[i].len=a[i].r-a[i].l; } sol1(); for(i=1; i<=n; ++i) for(j=1; j<=n; ++j) if(i!=j) { if(a[j].l<=a[i].l && a[j].r>=a[i].r) p[j]=1; } for(i=1, j=0; i<=n; ++i) if(p[i]) b[++j]=a[i].len; sort(b+1, b+j+1, [] (int x, int y) { return x>y; }); partial_sum(b+1, b+j+1, b+1); for(i=1, j=0; i<=n; ++i) if(!p[i]) a[++j].l=a[i].l, a[j].r=a[i].r; n=j; sort(a+1, a+n+1, [] (node x, node y) { return x.l<y.l; }); memset(f, 0x80, sizeof(f)); memset(g, 0x80, sizeof(g)); f[0][0]=0; g[0][0]=a[1].r; for(j=1; j<=n; ++j) { mx=0; for(i=0; i<j; ++i) mx=max(mx, g[i][j-1]); for(i=j; i<=n; ++i) { f[i][j]=max(0ll, mx-a[i].l); g[i][j]=f[i][j]+a[i+1].r; mx=max(mx, g[i][j-1]); } } for(j=0; j<=m; ++j) ans=max(ans, f[n][j]+b[m-j]); printf("%lld", ans); return 0; }