USACO2024DEC 银组 T2 解题报告

· · 题解

一道十分类似 P11232 [CSP-S 2024] 超速检测 的题，其他题解做法已经讲的很明白了，这里给出一种差分约束的解法。

题目分析

观察到坐标很大，先进行离散化。

考虑建立一个前缀和数组 pre，要最小化 pre_n，那么跑最长路。

于是对于一条限制 i，先求出 l_i,r_i 偏移后的下标 l_i',r_i'，可以看做一个点的编号。

那么应该满足的不等关系为：

r_i'-l_i' \geq t_i

于是建一条从 l_i' 到 r_i'，边权为 t_i 的边。

同时，为了满足解是满足条件的，还要加上一些附加限制：

0 \leq pre_i-pre_{i-1} \leq 1

最后跑一遍 spfa，n-dis_n 就是最终答案。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
inline int read()
{
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int maxn=3e5+10;
int T,n,k,pos[maxn],tmp[maxn];
struct node
{
    int v,w;
};
vector<node> G[maxn];
int dis[maxn],inq[maxn];
void spfa(int s)//差分约束spfa
{
    memset(inq,0,sizeof inq);
    fill(dis,dis+n+1,-1e18);
    queue<int> Q;
    Q.push(s);
    dis[s]=0,inq[s]=1;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop(),inq[u]=0;
        for(node &k:G[u])
        {
            int v=k.v,w=k.w;
            if(dis[v]<dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!inq[v])
                {
                    Q.push(v),inq[v]=1;
                }
            }
        }
    }
}

signed main()
{
    #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    #endif
    T=read();
    while(T--)
    {
        memset(pos,0,sizeof pos);
        memset(tmp,0,sizeof tmp);//多测清空
        n=read(),k=read();
        for(int i=1;i<=n;++i)
        {
            tmp[i]=pos[i]=read();
        }
        sort(tmp+1,tmp+n+1);
        for(int i=1;i<=n;++i)
        {
            pos[i]=lower_bound(tmp+1,tmp+n+1,pos[i])-tmp;
        }
        for(int i=1,l,r,t;i<=k;++i)
        {
            l=read(),r=read(),t=read();
            l=lower_bound(tmp+1,tmp+n+1,l)-tmp,r=upper_bound(tmp+1,tmp+n+1,r)-tmp-1;
            G[l-1].push_back({r,t});//注意在前缀和数组下表表示中，l要-1
        }
        for(int i=1;i<=n;++i)
        {
            G[i-1].push_back({i,0});
            G[i].push_back({i-1,-1});
        }//附加条件，见上
        spfa(0);
        cout<<n-dis[n]<<endl;
        for(int i=0;i<=n;++i) G[i].clear();
    }
    return 0;
}