题解：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)

，那么无论右端点怎么向右移，一定不可能再合法了，直接剪枝。
~~献上我的优良代码：~~

代码：

CPP

#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;
}

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

文章操作

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

闲话：

题意：

思路：

代码：

相关推荐

评论

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