『FLA - III』Wrestle

· · 题解

动态规划、前缀和

我出的第一道题。

Subtask #1

枚举选择了哪些蓝色线段，由于 l_i,r_i,L_i,R_i 的值域小，容易判断选择当前选择方案是否合法，如果合法则更新答案。

时间复杂度 O(n2^m)。

Subtask #2

在权值和上限 k 的限制下计算最优答案，容易发现这是一个背包问题，考虑动态规划。称与一条蓝色线段有交的所有红色线段权值和为这条蓝色线段的重量，一条蓝色线段与所有红色线段的交集包含的整点数量为这条蓝色线段的价值。

struct Segment{int l,r,w,v;}a[205],b[205];
//a:红色线段 b:蓝色线段 w:权值&重量 v:价值

设计 dp_{i,j} 为在前 i 条蓝色线段中选择若干线段，选择了第 i 条线段或者没有选择任何线段、方案合法且被选线段重量之和为 j 时能得到的最大价值。

如何保证选择方案合法？对于每条蓝色线段枚举所有红色线段，如果两条线段有交则将红色线段“拼”在蓝色线段上，把它们交集中的整点计入蓝色线段的价值，把红色线段的权值计入蓝色线段的重量。

for(int i=1;i<=m;i++){
    auto it=b[i];//判断是否相交不能用拼接后的线段
    for(int j=1;j<=n;j++){
        if(it.l>a[j].r||it.r<a[j].l) continue;
        b[i].l=min(b[i].l,a[j].l);
        b[i].r=max(b[i].r,a[j].r);
        b[i].w+=a[j].w;
        b[i].v+=min(it.r,a[j].r)-max(it.l,a[j].l)+1;
    }
}

这样处理之后，只要拼接后的两个蓝色线段不相交就可以进行状态转移了。在转移之前将蓝色线段按照左端点位置排序可以保证状态根据线段的位置从左到右转移。

int dp[205][205];
sort(b+1,b+m+1,[](auto x,auto y){return x.l<y.l;});
for(int i=1;i<=m;i++){
    for(int j=1;j<=i-1;j++) if(b[i].l>b[j].r){
        for(int q=k;q>=b[i].w;q--) dp[i][q]=max(dp[i][q],dp[j][q-b[i].w]+b[i].v);
    }
}

答案即为 dp 数组中的最大值，时间复杂度 O(nm+m^2k)。

Subtask #3

拼接线段部分的时间复杂度为 O(nm)，可以接受，考虑优化 O(m^2k) 的状态转移。

容易发现如果排序后线段 j 能转移到线段 i，那么所有下标比 j 小的线段都能转移到线段 i。预处理右端点最大的能够转移到 i 的线段编号，记为 pre_i。

修改状态定义，使得 dp_{i,j} 表示在前 i 条蓝色线段中选择若干线段，方案合法且被选线段重量之和为 j 时能得到的最大价值，找到下标最大的能转移到 i 的线段转移。

for(int i=1;i<=m;i++)
    for(int j=1;j<=m-1;j++) if(b[i].l>b[j].r) pre[i]=j;
for(int i=1;i<=m;i++){
    for(int j=1;j<=k;j++) dp[i][j]=dp[i-1][j];//继承上一状态
    for(int j=k;j>=b[i].w;j--) dp[i][j]=max(dp[i][j],dp[pre[i]][j-b[i].w]+b[i].v);
    for(int j=1;j<=k;j++) ans=max(ans,dp[i][j]);
}

时间复杂度 O(nm+mk)。

Subtask #4

可以发现拼线段是为了找到能转移到线段 i 的最大的线段 j 的编号，考虑预处理这个信息。在排序之后使用前缀和加二分快速统计无权值线段的重量和价值。

总体时间复杂度 O(n \log n +mk)。

#include<bits/stdc++.h>
using namespace std;
struct Segment{int l,r,v;long long w;}a[200005],b[5005];
int n,m,k,ans,cnt,ri[5005],pre[5005],sumv[200005],p[400005],dp[5005][5005];
long long sumw[200005];
bool cmp(const Segment &x,const Segment &y){return x.l<y.l;}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r>>a[i].w;
    for(int i=1;i<=m;i++) cin>>b[i].l>>b[i].r;
    sort(a+1,a+n+1,cmp),sort(b+1,b+m+1,cmp);
    for(int i=1;i<=n;i++){
        a[i].v=a[i].r-a[i].l+1;
        sumw[i]=sumw[i-1]+a[i].w;
        sumv[i]=sumv[i-1]+a[i].v;
        p[i*2-1]=a[i].l,p[i*2]=a[i].r;
    }
    for(int i=1;i<=m;i++){
        if(b[i].l>a[n].r||b[i].r<a[1].l) continue;
        int l=lower_bound(p+1,p+n*2+1,b[i].l)-p;
        int r=upper_bound(p+1,p+n*2+1,b[i].r)-p-1;
        if(l%2==1&&p[l]>b[i].r||r%2==0&&p[r]<b[i].l) continue;
        l=(l+1)/2,r=(r+1)/2,ri[i]=r;
        for(int j=1;j<=i-1;j++) if(ri[j]<l) pre[i]=j;
        b[i].w=sumw[r]-sumw[l-1];
        if(l!=r){
            b[i].v=sumv[r]-sumv[l-1]-a[r].v-a[l].v;
            b[i].v+=min(b[i].r,a[l].r)-max(b[i].l,a[l].l)+1;
            b[i].v+=min(b[i].r,a[r].r)-max(b[i].l,a[r].l)+1;
        }
        else b[i].v=min(b[i].r,a[l].r)-max(b[i].l,a[l].l)+1;
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=k;j++) dp[i][j]=dp[i-1][j];
        for(int j=k;j>=b[i].w;j--){
            dp[i][j]=max(dp[i][j],dp[pre[i]][j-b[i].w]+b[i].v);
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans<<'\n';
    return 0;
}