[Luogu] 选择客栈

https://www.luogu.org/problemnew/show/P1311

思路就是，从1到n枚举，输入color和price的值，我们需要记录一个距离第二个客栈最近的咖啡厅价钱合理的客栈位置，用一个now变量记录。

开三个辅助数组，last[i]表示最后一个以i为颜色的客栈的位置，cnt[i]表示以i为颜色的客栈总数，sum[i]可以看作是一个临时数组，用来存储当前的方案数。

可以这么想，当前枚举到一个客栈i，这个i是第二个客栈，那么显然第一个客栈一定在第二个客栈之前，编号必定是0~i-1之间的一个数。如果我发现枚举的时候在某一个客栈前面有一个价钱合理的咖啡厅，那么在这之前的任何一个同色客栈都是第一个客栈可以选的，那么统计一下数量，这就是当前的方案数。

然后更新last数组，更新ans，让cnt[color]++，这样从左到右地推过来就好了。

这个解法简化于暴力算法，暴力算法要循环三层，一层1客栈，二层2客栈，3层合理的位置，这样做显然不行，而我们做的就是去优化掉两层，而是从枚举2客栈出发推出1客栈的位置和所有可行方案，所以这样做是正确的。最后输出即可。

#include<cstdio>

#include <iostream>

const int N = ;

#define gc getchar() 

inline int read() {

    int x = ; char c = gc;

    while(c < '' || c > '') c = gc;

    while(c >= '' && c <= '') x = x *  + c - '', c = gc;

    return x;

}

int n,k,p,col,mon,now,ans;

int num[N],s[N],c[N];

int main() {

    n = read(); k = read(); p = read();

    for(int i = ; i <= n; ++ i) {

        col = read(); mon = read();

        if(mon <= p) now = i;

        if(now >= c[col]) s[col] = num[col];

        c[col] = i;

        ans += s[col];

        num[col] ++;

    }

    printf("%d", ans);

    return ;

}

巴特西

[Luogu] 选择客栈

最新文章

热门文章