题目 | Array Painting
Educational Codeforces Round 152 (Rated for Div. 2)
D. Array Painting
https://codeforces.com/contest/1849/problem/D
2 seconds / 256 megabytes
standard input / standard output
Problem
You are given an array of
Your goal is to paint each element of the array red. In order to do so, you can perform operations of two types:
- pay one coin to choose a blue element and paint it red;
- choose a red element which is not equal to
and a blue element adjacent to it, decrease the chosen red element by , and paint the chosen blue element red.
What is the minimum number of coins you have to spend to achieve your goal?
Input
The first line contains one integer
The second line contains
Output
Print one integer — the minimum number of coins you have to spend in order to paint all elements red.
Examples
Input
3
0 2 0
Output
1
Input
4
0 0 1 1
Output
2
Input
7
0 1 0 0 1 0 2
Output
4
Note
In the first example, you can paint all elements red with having to spend only one coin as follows:
- paint the
-nd element red by spending one coin; - decrease the
-nd element by and paint the -st element red; - decrease the
-nd element by and paint the -rd element red.
In the second example, you can paint all elements red spending only two coins as follows:
- paint the
-th element red by spending one coin; - decrease the
-th element by and paint the -rd element red; - paint the
-st element red by spending one coin; - decrease the
-rd element by and paint the -nd element red.
题解
首先,对于不为
- 第
位为 :花一个硬币“激活”为后,只有第 位变红,总区间为 。 第
位为 :花一个硬币“激活”为后,除了第 位变红还有:- 如果选择左侧,则从第
位开始到左侧第一个 结束都能链式变红,总区间为 . - 如果选择右侧,则从第
位开始到右侧第一个 结束都能链式变红,总区间为 .
- 如果选择左侧,则从第
第
位为 :花一个硬币“激活”为后,除了第 位变红还有:- 对于左侧,从第
位开始到左侧第一个 结束都能链式变红。 - 对于右侧,从第
位开始到右侧第一个 结束都能链式变红。 - 总区间为
- 对于左侧,从第
从左到右扫描一遍每个点,将每个点能够变红的区间储存下来,对于每个区间,使用
代码
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 10);
for (int i = 1; i <= n; i++)
cin >> a[i];
vector<int> pre(n + 10), nxt(n + 10);
for (int i = 1; i <= n; i++)
{
if (a[i - 1])
pre[i] = pre[i - 1];
else
pre[i] = i - 1;
}
for (int i = n; i >= 1; i--)
{
if (a[i + 1])
nxt[i] = nxt[i + 1];
else
nxt[i] = i + 1;
}
// for (int i = 1; i <= n; i++)
// cout << pre[i] << " \n"[i == n];
// for (int i = 1; i <= n; i++)
// cout << nxt[i] << " \n"[i == n];
vector<pair<int, int>> pv;
for (int i = 1; i <= n; i++)
{
if (a[i] == 0)
{
pv.push_back({i, i});
}
else if (a[i] == 1)
{
pv.push_back({i, nxt[i]});
pv.push_back({pre[i], i});
}
else // if (a[i] == 2)
{
pv.push_back({pre[i], nxt[i]});
}
}
sort(pv.begin(), pv.end());
int ans = 0, idx = 0;
for (int i = 1; i <= n; i++)
{
int l = -1, r = -1;
for (; idx < pv.size(); idx++)
{
if (!(l == -1 || pv[idx].first <= i))
break;
l = pv[idx].first;
r = pv[idx].second;
}
ans += max(0LL, l - i);
ans++;
i = r;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
本文采用 CC BY-SA 4.0 许可,本文 Markdown 源码:Haotian-BiJi