Atcoder-Beginner-Contest-#263D题解

发表于 分类于 ， ， ，

Atcoder Beginner Contest #263 D - Left Right Operation

题目大意

给定一串长度为nn的数列, 可以进行如下操作, 每种最多一次:

  • 将A1A2⋯AiA_1 A_2 \cdots A_i赋值为LL
  • 将AjAj+1⋯AnA_j A_{j+1} \cdots A_n赋值为RR

求出操作后数列AA的最小值

数据规模

1≤N≤2⋅1051 \leq N \leq 2 \cdot 10^5

−109≤L,R≤109-10^9 \leq L,R \leq 10^9

−109≤Ai≤109-10^9 \leq A_i \leq 10^9

N,L,R,A∈ZN,L,R,A \in \mathbb{Z}

我的思路(错)

对于数列AA,处理出前缀和le和后缀和ri

从前往后遍历, 求出从头替换的数列最小值及其替换位置pos1

从后往前遍历, 求出从尾替换的数列最小值及其替换位置pos2

然后比较pos1和pos2的大小, 分情况讨论

大佬代码

heno239

对于数列AA变换后的数列A′A'的每一位Ai′A'_i, 只有三种可能:

  1. 被填充为RR
  2. 保持不变
  3. 被填充为RR

且三种情况必须顺次出现.

所以对于每一位数字, 对应每种情况存在三个状态, 且每个状态只能转移到大于等于该状态编号的状态:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
rep(i, n)
{
	vector<ll> ndp(3, INF);
	for (int x = 0; x < 3; x++)
		for (int y = x; y < 3; y++)
		{
			ll cost;
			if (y == 0)
				cost = l;
			else if (y == 1)
				cost = a[i];
			else
				cost = r;
			chmin(ndp[y], dp[x] + cost);
		}
	swap(dp, ndp);
}

时间复杂度Θ(N)\Theta(N)

hank55663

代码非常简短.

预处理ans = r * n

对于每一位数字, 计算其前缀和的最小值pre = min(pre + a[i], (i + 1) * l);,同时计算出答案ans = min(ans, (n - i - 1) * r + pre);

时间复杂度Θ(N)\Theta(N)

hitonanode

预处理数组left和right:

  • left[i] 表示若将数列AA从头至第i位替换为LL, 与原数组的差
  • right[i]表示若将数列AA从第i为至末尾替换为RR, 与原数组的差

对于每一位i，寻找数列和加上left[i]以及从此位至末尾最小的right[j]的值，记录并更新答案

时间复杂度Θ(N)\Theta(N)