P11232

koobee · 2024-11-09 17:27:10 · 题解

这里给大家介绍一种与众不同的做法。

考场上：这个题怎么做？看起来是区间问题。

线段树维护？不太会。

贪心？蒟蒻没想到。

动态规划？貌似可以。

先把所有被判为超速的车找出来，在把每个车的“超速区间”（如果一辆车的超速区间中有摄像头，那么这辆车被判为超速）算出来，设为 [l_1,r_1] 到 [l_{ans},r_{ans}]。（ans 为初始被判为超速的车辆）

问题被我们转换了：有 ans 个区间，m 个位置，每个区间里面必须有位置被选，求最少的被选位置的数量。

初始的状态设计：dp_{i,j} 为考虑前 j 个区间，前 i 个位置（1\le i\le m）中最少被选位置的数量。

这个做法可以拿 80 分，但空间时间都炸了。尝试优化空间。

改进的状态设计：dp_i 表示 考虑右端点 \le i 的区间，在前 i 个位置中最少的被选点数量。

这个做法很难被卡，民间和官方都能拿 100 分，但我还是建议大家用树状数组优化成时间复杂度符合要求的代码。

这是刚才那个思路的代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5, M = 1e6+5;
int T, n, m, l, v, ans, mn, sz, st, s[M], t[M], p[N], dp[M];
struct node{
    int d, v, a, l, r, f;
} c[N];
struct npd{
    int l, r;
    bool operator >(const npd &b) const{
        if(l != b.l) return l < b.l;
        return r < b.r;
    }
} x[N];
bool cmp(npd x, npd y){
    if(x.r != y.r) return x.r < y.r;
    return x.l < y.l;
}
int main(){
    //freopen("detect.in", "r", stdin);
    //freopen("detect.out", "w", stdout);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>T;
    while(T--){
        memset(s, 0, sizeof(s));
        memset(t, 0, sizeof(t));
        memset(dp, 0, sizeof(dp));
        mn = 1e9, ans = 0, sz = 0, st = 0;
        cin>>n>>m>>l>>v;
        for(int i = 1; i <= n; i++) c[i].f = 0, c[i].l = c[i].r = -1;
        for(int i = 1; i <= n; i++){
            cin>>c[i].d>>c[i].v>>c[i].a;
            if(c[i].a <= 0 && c[i].v <= v) continue;
            if(c[i].a == 0) c[i].l = c[i].d, c[i].r = l;
            else{
                double t = 1.0 * fabs((v - c[i].v)) / fabs(c[i].a) * 1.0;
                if(c[i].a > 0){
                    if(c[i].v > v) c[i].l = c[i].d, c[i].r = l;
                    else{
                        double len = t * (1.0 * v + c[i].v) / 2.0 + c[i].d;
                        if(int(len) + 1 <= l) c[i].l = int(len) + 1, c[i].r = l;
                    }
                }
                else{
                    double len = t * (1.0 * v + c[i].v) / 2.0 + c[i].d;
                    c[i].l = c[i].d, c[i].r = min(int(ceil(len) - 1), l);
                }
            }

        }
        for(int i = 1; i <= m; i++){
            cin>>p[i];
            t[p[i]] = 1;
        }
        for(int i = 1; i <= l; i++) t[i] += t[i-1];
        for(int i = 1; i <= n; i++){
            int num;
            if(c[i].l == 0) num = 0;
            else num = t[c[i].l-1];
            if(c[i].l >= 0 && c[i].r >= 0 && t[c[i].r] - num > 0) c[i].f = 1, ans++, x[++sz] = {c[i].l, c[i].r}, st = max(st, c[i].l);
        }
        cout<<ans<<" ";
        sort(x+1, x+1+sz, cmp);
        int j = 1, k = 1;
        priority_queue<npd, vector<npd>, greater<npd> > q;
        for(int i = 1; i <= m; i++){
            while(j <= sz && x[j].r < p[i]) q.push((npd){x[j].l, x[j].r}), j++;
            while(k < i && !q.empty() && p[k] < q.top().l) k++;
            if(!q.empty() && k < i){
                int tmp = 1e9;
                for(int ll = k; ll < i; ll++) tmp = min(tmp, dp[ll]);
                dp[i] = tmp + 1;
            }
            else dp[i] = 1;
        }
        st = lower_bound(p+1, p+1+m, st) - p;
        for(int i = st; i <= m; i++) mn = min(mn, dp[i]);
        if(ans != 0) cout<<m - mn<<"\n";
        else cout<<m<<"\n";
    }
    return 0;
}