题解 P1311 【选择客栈】

· · 题解

题目大意

给定n个数和一个整数p，每个数有两个值a,k。

对于任意的两个数i,j

求使得min\{a[i],a[i+1],...,a[j]\}\le p 并且k[i]=k[j]的方案总数。

题解

显然的一道dp（其实就是个递推？）

设f[i] 为选择第i个客栈，有f[i]种方案。

60分的话是挺好想的。

我们考虑O(n^2)的转移

for(int i = 1 ; i <= n ; ++ i) {
    for(int j = 1 ; j < i ; ++ j) {
        if(a[j] == a[i] && min[i,j] <= p) f[i] ++;
    }
}

显然min[i,j]可以用log级别的算法维护，那么算法复杂度就是O(n^2logn)，就可以拿到60分的好成绩。

我们考虑进一步优化。（优化成了更加优雅的暴力）

考虑到i之前的第一个与i颜色相同的住宿，可以对f[i]产生贡献。

设g[i]为最后一个颜色为i的点的编号

设col[i]为结点i的颜色

显然的一点是f[i]一定可以从 f[\ g[col[i]]\ ] 继承过来的。

那么我们开始可以先让 f[i] = f[\ g[col[i]]\ ]

然后如果我们发现 min[\ g[\ col[i]\ ]\ ,\ i] \le p 时,

显然 ， 这时候前面所有和他编号相同的店铺都可以选到

因此此时让f[i]等于i之前和i颜色相同的店铺个数即可。

最后把$f[i]$扫一遍即可。 $min$值显然可以用$ST$表或者线段树维护。 时间复杂度$O(nlogn)

（想不到线性做法的蒟蒻只能用数据结构硬怼）

Code: 
//优雅的暴力
#include <bits/stdc++.h>
#define ls(x) x << 1
#define rs(x) x << 1 | 1
using namespace std;

const int maxn = 200000 + 10;

int n , k , p;
int f[maxn] , g[maxn] , num[maxn];

struct Node {
    int val , col;
}a[maxn];

struct Segment_Tree {
    int l , r , dis;
}t[maxn << 2];

void pushup(int x) {t[x].dis = min(t[ls(x)].dis , t[rs(x)].dis);}

void built(int x , int l ,int r ) {
    t[x].l = l , t[x].r = r;
    if(l == r) {t[x].dis = a[l].val; return;}
    int mid = (l + r) >> 1;
    built(ls(x) , l , mid); built(rs(x) , mid + 1 , r);
    pushup(x);
}

int query(int x, int  l, int r) {
    if(t[x].l >= l && t[x].r <= r) {return t[x].dis;}
    int mid = (t[x].l + t[x].r) >> 1;
    int ans = 0x7fffffff;
    if(l <= mid) ans = min(ans , query(ls(x) , l , r));
    if(r  > mid) ans = min(ans , query(rs(x) , l , r));
    return ans;
}

int main () {
    scanf("%d%d%d" ,&n , &k ,&p);
    for(int i = 1 ; i <= n ; ++ i) {
        scanf("%d%d", &a[i].col , &a[i].val);
        if(!g[a[i].col]) g[a[i].col] = i;
    }
    built(1 , 1 , n);
    for(int i = 1 ; i <= n ; ++ i) {
        f[i] = f[g[a[i].col]];
        if(i == g[a[i].col]) {num[a[i].col] ++;continue;}
        if(query(1 , g[a[i].col] ,i) <= p) f[i] = num[a[i].col];
        g[a[i].col] = i;
        num[a[i].col] ++;
    }

    int ans = 0;
    for(int i = 1 ; i <= n ; ++ i) {
        ans += f[i];
    }
    printf("%d\n" , ans);
    return 0;
}