题解：P14567 【MX-S12-T2】区间

· · 题解

前言

2s 时间完全没必要，1s 即可做好了，平方算法加退火也让别人拿到满分，没有一个超时 hack 数据，这让我们 O(n) 的人怎么办。按道理讲我的算法时严格为 O(n) 的后面加 hack 数据应该不会让我错。

思路

一道贪心题。

由于 f_i 是单调不降的，则对于一个为如：

2 3 4 4 3 2

的数据坑定是取 4 4 时答案为最小，否则取如 3 4 4 3 时 4 4 被更大的 f_i 求值了。

这样就如括号一样，如 ((()))(()) ，只要取并列括号中最中间最小的即可。 ((())) 中，只需要取最中间的括号即可。

由此只要用栈来找最中间的括号，然后求值取最小即可。

不懂看代码注释吧。

CODE

int n, i;
int a[1000100], e[1000100], pos[1000100];
LL val[1000100], f[1000100];
bool h[1000100];
LL mi = 1e18;
int top;
int stk[1000100], id[1000100];
void get(int l, int r) {
    LL ans = 0;
    for (int i = l; i <= r; ++i)
        ans += val[i] * f[i - l + 1];
    mi = min(mi, ans);
}
int main () {
    n = read();
    for (i = 1; i <= n; ++i) a[i] = read();
    for (i = 1; i <= n; ++i) val[i] = 1ll * read(), ++e[a[i]], h[a[i]] = 1; // e保存数量 
    for (i = 1; i <= n; ++i) f[i] = 1ll * read();

    for (i = 1; i <= n; ++i) {
        int x = a[i];
        if(h[x] == 1) //h为是否在此之前加入过栈中 
            pos[x] = i, h[x] = 0; //pos记录最早出现的位置 

        stk[++top] = x; id[top] = i; --e[x]; //入栈 

        bool flag = false;
        while(top > 0 && e[stk[top]] == 0) //全部如栈了弹出 
            --top, flag = true; //括号匹配成功才做后面 

        if(flag && e[stk[top + 1]] == 0 && pos[stk[top + 1]] == id[top + 1]) { // 这一种类结束，且已经全部弹完，求值 
            get(id[top + 1], i); //求答案 
            top = 0; //贪心，((()))只要取最中间的即可剩下外边的直接弹出栈 
        }

    }
    printf("%lld", mi);
}