题解：P12302 [ICPC 2023 WF] 时差

· · 题解

一道好题。

一个贪心的想法是，显然我会希望在某个活动结束后立即睡觉，这样我的可操作空间最大。但是这不行，因为如果活动结束的时刻落在 [k,2k) 之内就不一定可以睡。

考虑一个关键点：如果我们现在在 [2k,3k] 阶段，那么我们是可以想睡就睡的。

所以我们只需要想办法让活动结束在这个阶段内就行。考虑一个结束在 [k,2k) 的活动，如果我希望在这个活动结束后睡觉，那么我只需要减小上一次睡觉的时间就行了！因为睡觉时间可以取任何正整数，而此处 k\ge 2，所以一定可以通过调整使得活动结束在 [2k,3k] 内部。

于是我们得出结论：只要有方案，一定存在一种方案使得我必然总是在活动结束后睡觉。

考虑 dp。f_i 表示在第 i 个活动后立即睡觉是否可行。那么考虑转移：f_i 处尝试从第 j 个活动结束后开始立即睡觉，睡觉时间可以取 t\in(0,b_{j+1}-e_j] 的任何数，并要求保持清醒直到 e_i。显然，只要满足 e_i-e_j\le 3(b_{j+1}-e_j) 就一定可以找到一个满足要求的 t（这个条件说明我们至少存在一个可取的 t，我们前面已经说明总是可以调整得到一个 t 使得 e_i\in[2t,3t]）。

于是转移是：

f_i\gets f_j,\ \ j<i\land e_i-e_j\le 3(b_{j+1}-e_j)

我们可以在 dp 过程中记录转移项，然后在最后往回构造。往回构造就是两个不等式，一个限制我们必须在活动结束时位于 [2t,3t]，一个限制 t，随便解一下就行。

于是我们获得了一个 \mathcal O(n^2) 的做法：

int n;
int dp[N];
int lst[N];
ll b[N],e[N];
vector <pll> ans;
int main(){
#ifdef Shun
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>n;
    fr1(i,1,n) cin>>b[i]>>e[i];
    dp[0]=1;
    fr1(i,1,n){
        fr2(j,i-1,0){
            if(dp[j]&&(e[i]-e[j])<=3*(b[j+1]-e[j])){
                lst[i]=j;
                dp[i]=1;
                break;
            }
        }
        // cout<<dp[i]<<endl;
    }
    if(!dp[n]) cout<<"impossible\n";
    else{
        int x=n;
        while(x){
            int id=lst[x];
            ll t=b[id+1]-e[id];
            ll T=e[x]-e[id];
            // cout<<t<<" "<<T<<endl;
            ll k=(T+2)/3;
            ans.push_back({e[id],e[id]+k});
            x=lst[x];
        }
        reverse(ans.begin(),ans.end());
        cout<<ans.size()<<'\n';
        for(auto i:ans) cout<<i.fi<<" "<<i.se<<'\n';
    }
    ET;
}
//ALL FOR Zhang Junhao.

转移显然可以优化，移项之后形如 e_i\le \text{Poly}(j)，由于右侧是一个只关于 j 的多项式，所以我们动态维护它的最大值和最大值位置就可以了。只需将 dp 部分改为下面这样即可通过：

maxn=3*b[1];
fr1(i,1,n){
    if(e[i]<=maxn) dp[i]=1,lst[i]=tf;
    if(dp[i]){
        ll coef=3*b[i+1]-2*e[i];
        if(maxn<coef) maxn=coef,tf=i;
    }
    // cout<<dp[i]<<endl;
}

时间复杂度 \mathcal O(n)。