P1068 · OFFICIAL SOLUTION

P1068 梦的七重回旋官方题解

Gioush OJ · P1068 梦的七重回旋

【部分分：测试点 111】

每个片段有编入第一条梦轨、编入第二条梦轨和舍弃三种选择。直接枚举全部 $3^n$ 种选择，检查两条梦轨之间是否存在正长度的重叠。
对每个合法方案统计两条梦轨的片段数量，既可以更新没有额外限制的答案，也可以更新方案中每个已选片段的强制答案。时间复杂度为 $\mathcal{O}(3^n n^2)$ 。

【性质观察】

只需要关心片段的开始与结束时刻。将全部端点离散化后，端点数量记为 $m$ ，有 $m\leq 2n$ 。令 $c_{l,r}$ 表示起止时刻都完整落在 $[l,r]$ 中的片段数量。
扫描一组合法方案时，两条梦轨占用的时间可以切成若干首尾相接的时间段，每一段只交给其中一条梦轨。若一段已经交给某条梦轨，那么把所有完整落在这一段中的片段都加入该梦轨不会破坏合法性，也不会使平衡度变小。

【评分方式 A】

定义 $f_{i,j}$ 表示只考虑时刻 $1\sim i$ ，第一条梦轨恰好得到 $j$ 个片段时，第二条梦轨最多能够得到多少个片段。初值为 $f_{0,0}=0$ ，其余状态均为负无穷。
枚举最后一段时间 $[k,i]$ 。将其中全部 $c_{k,i}$ 个片段交给第二条梦轨，或者交给第一条梦轨，可以得到

f_{i,j}=\max_{0\leq k\leq i} \begin{cases} f_{k,j}+c_{k,i},\\ f_{k,j-c_{k,i}} & j\geq c_{k,i}. \end{cases}

为了处理强制包含片段的询问，再定义完全对称的后缀状态 $g_{i,j}$ ：只考虑时刻 $i\sim m$ ，第一条梦轨恰好得到 $j$ 个片段时，第二条梦轨最多能够得到多少个片段。
边界为 $g_{m+1,0}=0$ ，其余状态为负无穷，完整转移为

g_{i,j}=\max_{i\leq k\leq m+1} \begin{cases} g_{k,j}+c_{i,k},\\ g_{k,j-c_{i,k}} & j\geq c_{i,k}. \end{cases}

没有额外限制时的答案为 $\max_{0\leq j\leq n}\min\{j,g_{1,j}\}$ 。

【部分分：测试点 2∼32\sim 32∼3】

评分方式 A 只要求没有额外限制时的答案。为了继续处理每个片段必须被选中的限制，我们固定一个时间段 $[l,r]$ ，将其中全部片段交给第一条梦轨。再设第一条梦轨在左侧和右侧分别得到 $x,y$ 个片段，则两条梦轨最终能够得到的数量分别为

x+y+c_{l,r},\qquad f_{l,x}+g_{r,y}.

因此定义

h_{l,r}=\max_{0\leq x,y\leq n} \min\{x+y+c_{l,r},f_{l,x}+g_{r,y}\}.

枚举 $l,r,x,y$ 可以在 $\mathcal{O}(n^4)$ 的时间内求出全部 $h_{l,r}$ 。

设第 $i$ 个片段离散化后的端点为 $L_i,R_i$ 。只要 $l\leq L_i$ 且 $R_i\leq r$ ，第 $i$ 个片段就完整落在 $[l,r]$ 中，从而一定会被选入第一条梦轨。
所以第 $i$ 个强制答案为

Ans_i=\max_{l\leq L_i,\,r\geq R_i}h_{l,r}.

枚举包含它的时间段不会遗漏最优方案，因为在任意最优方案中，都可以取第一条梦轨覆盖该片段的连续时间段作为 $[l,r]$ 。

【正解】

上一档枚举 $x,y$ 的复杂度过高。计算 $h_{l,r}$ 时，固定 $l,r,x$ 。随着 $y$ 增大， $x+y+c_{l,r}$ 单调增大，而 $f_{l,x}+g_{r,y}$ 单调不增，因此两者的最小值只会先增大再减小，能够改进答案的 $y$ 位于两者的交界附近。
当 $x$ 增大时，第一项整体增大，而 $f_{l,x}$ 单调不增，所以这条改进边界只会向更小的 $y$ 移动。固定 $l,r$ 后，令 $p$ 从右端开始。按照 $x=0,1,\ldots,n$ 扫描，每次只枚举 $y=p,p-1,\ldots,0$ ，记录本轮最后一次改进 $h_{l,r}$ 的位置，再令 $p$ 移到该位置。
$c_{l,r}$ 可以在 $\mathcal{O}(n^3)$ 的时间内直接预处理。前缀与后缀动态规划各有 $\mathcal{O}(n^2)$ 个状态，每个状态枚举最后一段的端点，总时间复杂度为 $\mathcal{O}(n^3)$ 。
使用双指针后，全部 $h_{l,r}$ 的计算也是 $\mathcal{O}(n^3)$ 。最后枚举包含每个片段的 $l,r$ 仍为 $\mathcal{O}(n^3)$ 。因此总时间复杂度为 $\mathcal{O}(n^3)$ ，空间复杂度为 $\mathcal{O}(n^2)$ 。
端点相接不算正长度重叠，所以前后两段可以共用同一个离散化端点。所有不可达的动态规划状态必须初始化为负无穷。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/184Name:dream.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 41011using namespace std;12 13int c,T,n,Mapping[MAXN<<1],In1,In2,Ori[MAXN<<1],cnt1=0,cnt2=0,Ans1=0;14int Count[MAXN][MAXN],Pre[MAXN][MAXN],Suff[MAXN][MAXN],Sum[MAXN][MAXN];15 16void Discrete() {17    sort(Ori+1,Ori+cnt1+1);18    for (int i=1;i<=cnt1;i++) {19        if (i==1||Ori[i]!=Ori[i-1]) Mapping[++cnt2]=Ori[i];20    }21}22 23int Get(int x) {24    return lower_bound(Mapping+1,Mapping+cnt2+1,x)-Mapping;25}26 27struct seg{28    int l,r;29}S[MAXN];30 31void Solve() {32    cnt1=cnt2=Ans1=0;33    memset(Pre,0xcf,sizeof(Pre));34    memset(Suff,0xcf,sizeof(Suff));35    memset(Sum,0,sizeof(Sum));36    memset(Count,0,sizeof(Count));37    scanf("%d",&n);38    for (int i=1;i<=n;i++) {39        scanf("%d%d",&In1,&In2);40        S[i]={In1,In1+In2}; Ori[++cnt1]=In1;Ori[++cnt1]=In1+In2;41    }42    Discrete();43    for (int i=1;i<=n;i++) {S[i].l=Get(S[i].l);S[i].r=Get(S[i].r);}44    for (int i=0;i<=cnt2+1;i++) {45        for (int j=0;j<=i;j++) {46            for (int k=1;k<=n;k++) {47                if (S[k].l>=j&&S[k].r<=i) Count[j][i]++;48            }49        }50    }51    Pre[0][0]=0;52    Suff[cnt2+1][0]=0;53    for (int i=1;i<=cnt2;i++) {54        for (int j=0;j<=n;j++) {55            for (int k=0;k<=i;k++) {56                Pre[i][j]=max(Pre[i][j],Pre[k][j]+Count[k][i]);57                if (j-Count[k][i]>=0) Pre[i][j]=max(Pre[i][j],Pre[k][j-Count[k][i]]);58            }59        }60    }61    for (int i=cnt2;i>=1;i--) {62        for (int j=0;j<=n;j++) {63            for (int k=cnt2+1;k>=i;k--) {64                Suff[i][j]=max(Suff[i][j],Suff[k][j]+Count[i][k]);65                if (j-Count[i][k]>=0) Suff[i][j]=max(Suff[i][j],Suff[k][j-Count[i][k]]);66            }67        }68    }69    for (int i=0;i<=n;i++) Ans1=max(Ans1,min(i,Suff[1][i]));70    printf("%d\n",Ans1);71    for (int r=1;r<=cnt2;r++) {72        for (int l=1;l<=r;l++) {73            int p=cnt2,my=0;74            for (int cx=0;cx<=n;cx++) {75                for (int cy=p;cy>=0;cy--) {76                    if (Sum[l][r]<min(cy+cx+Count[l][r],Pre[l][cx]+Suff[r][cy])) {77                        my=cy; Sum[l][r]=min(cy+cx+Count[l][r],Pre[l][cx]+Suff[r][cy]);78                    }79                }80                p=my;my=0;81            }82        }83    }84    for (int i=1;i<=n;i++) {85        int Ans2=0;86        for (int j=1;j<=S[i].l;j++) {87            for (int k=S[i].r;k<=cnt2;k++) Ans2=max(Ans2,Sum[j][k]);88        }89        printf("%d\n",Ans2);90    }91}92 93int main() {94    scanf("%d%d",&c,&T);95    while (T-->0) Solve();96    return 0;97}