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

· · 题解

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

闲话：

本蒟蒻初二，冲刺 NOIP 一等奖。
赛时 10 分钟切了第一题，30 分钟切了第二题，然后就啥而不会了，喜提 210 分。

题意：

求一个代价最小的合法区间 [l, r] 。
合法区间的定义：任何一个出现在区间内的颜色都不能出现在区间外。

思路：

提供一个简单而又略带卡常的做法。
首先先打暴力，复杂度为 O(n^3) 。
考虑在暴力的基础上进行优化：
我们发现随着区间右端点逐渐递增，代价也逐渐递增，所以可以直接剪枝，即对于每一个左端点找到合法的下标最小的右端点并统计答案。
随着右端点的递增，如果发现存在颜色 x 和下标 i, j 满足 c_i = c_j = x 且 i \in [l, r]、j \in [1, l)，那么无论右端点怎么向右移，一定不可能再合法了，直接剪枝。
献上我的优良代码：

代码：

#include<bits/stdc++.h>

using namespace std;
#define I return
#define love 0
#define coding

int n,c[1000050],v[1000050],f[1000050],pre[1000050],lst[1000050],mx;
long long ans = 1e18+7;

inline long long calc(int x,int y){
    long long res = 0;
    for(int i = x;i <= y;++i) res+=(1LL*v[i]*f[i-x+1]);
    return res;
}
inline int rd(){
    int x = 0,f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x*10+ch-'0';
        ch = getchar();
    }
    return x*f;
}
inline void wt(long long x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9) wt(x/10);
    putchar(x%10+'0');
}

int main(){
//  freopen("T1.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    n = rd();
    for(int i = 1;i <= n;++i) c[i] = rd();
    for(int i = 1;i <= n;++i) v[i] = rd();
    for(int i = 1;i <= n;++i) f[i] = rd();
    for(int i = 1;i <= n;++i){
        lst[c[i]] = i;
        if(pre[c[i]]) continue;
        pre[c[i]] = i;
    }
    for(int i = 1;i <= n;++i){
        mx = 0;
        for(int j = i;j <= n;++j){
            mx = max(mx,lst[c[j]]);
            if(pre[c[j]] < i) j = n+1;
            else if(mx == j){
                ans = min(ans,calc(i,j));
                j = n+1;
            }
        }
    }
    wt(ans);
    I love coding;
    return 0;
}