萌新的第一篇题解
题目大意
对于一个初始颜色都为蓝色的数组 \(a_1,a_2,\dots,a_n\) 其中 \(a_n \in \{0,1,2\}\),现在可以进行两个操作:
- 花费 \(1\) 个金币,将 \(a_i\) 涂成红色;
- 选择一个红色的 \(a_i > 0\),将 \(a_{i-1}\) 或 \(a_{i+1}\) 涂成红色,同时 \(a_i\) 减 \(1\)。
输出金币的最小数目。
动态规划
由于操作二只能对其左右的格子产生影响,故而我们考虑动态规划,将其转换为一个 \(01\) 背包问题。同时,我们还需要维护格子的数字 \(a_i\),故而设计一个三维数组。
\[d[i][j][k] \ \ \ \ (j\in \{0,1\}, \ k \in \{0, 1, 2\}且k \leqslant a_i) \]转移到 \(d[a_i]\) 时,\(a_i\) 之前的都被涂过。
当 \(j = 0\) 时说明 \(a_i\) 暂时还未被涂过,\(j = 1\) 时说明 \(a_i\) 已经被涂过了。
\(k = a_i\) 说明 \(a_i\) 没有通过操作二涂他左侧的那格,此时只能从 \(d[a_{i-1}][1]\) 转移过来;\(k = a_i - 1\) 说明 \(a_i\) 涂了他左边的那格,此时只能从 \(d[a_{i-1}][0]\) 转移过来。
\[\begin{aligned}d[i][1][a_i]&=\min \begin{cases} d[i-1][1][a_{i-1}] + 1&(a_{i-1}=0)\ \ \ \small{直接涂a_i格,耗费一金币}\\ d[i-1][1][a_{i-1}]&(a_{i-1}>0) \ \ \ \small{让没涂过 a_{i-2} 的 a_{i-1}涂a_i}\\ d[i-1][1][a_{i-1}-1]&(a_{i-1}>1) \ \ \ \small{让涂过 a_{i-2} 的 a_{i-1}涂a_i} \end{cases}\\ d[i][1][a_i - 1]&=\min \begin{cases} d[i-1][0][a_{i-1}] + 1&(a_i>0,a_{i-1}=0)\ \ \ \small{直接涂a_i格,耗费一金币,同时让a_i涂a_{i-1}}\\ d[i-1][0][a_{i-1} - 1] + 1&(a_i>0,a_{i-1}>0)\ \ \ \small{同理,但这里是涂过a_{i-2}的a_{i-1}} \end{cases}\\ d[i][0][a_i]&=\min \begin{cases} d[i-1][1][a_{i-1}]&\ \ \ \small{不涂a_i格,a_{i-1} 没涂 a_{i-2}}\\ d[i-1][1][a_{i-1}-1]&(a_{i-1}>0)\ \ \ \small{不涂a_i格,a_{i-1} 涂过 a_{i-2}} \end{cases}\\ d[i][0][a_i-1]&=\min \begin{cases} d[i-1][0][a_{i-1}]&(a_i>0,a_{i-1}=0)\ \ \ \small{不涂a_i格,之后让a_i 涂 a_{i-1}}\\ d[i-1][0][a_{i-1}-1]&(a_i>0,a_{i-1}>0)\ \ \ \small{同理,但这里涂过 a_{i-2} 的 a_{i-1}} \end{cases}\end{aligned}\]进行初始化
\[\begin{aligned} a_0 &= 0,\\ d[0][1][0] &= 0,\\ d[0][0][0] &= INF \end{aligned} \]由于最后一格 \(a_n\) 必须要被涂,故
\[ans=\min \begin{cases} d[n][1][a_{n}]&(a_{n}=0)\\ d[n][1][a_{n} - 1]&(a_{n}>0) \\ \end{cases}\\ \]代码
#include<bits/stdc++.h>
using namespace std;
#define fr(a, b, i) for (int i = a; i <= b; i++)
#define Fr(a, b, i) for (int i = a; i < b; i++)
#define rf(a, b, i) for (int i = a; i >= b; i--)
#define rF(a, b, i) for (int i = a; i > b; i--)
int n, a[200010], d[200010][2][3];
int main()
{
cin >> n;
fr(1, n, i) cin >> a[i];
d[0][1][0] = 0;
d[0][0][0] = 9999999;
fr(1, n, i){
d[i][1][a[i]] = d[i - 1][1][a[i - 1]] + 1;
if(a[i - 1] > 0)
d[i][1][a[i]] = min(d[i - 1][1][a[i - 1]], d[i][1][a[i]]);
if(a[i - 1] > 1)
d[i][1][a[i]] = min(d[i - 1][1][a[i - 1] - 1], d[i][1][a[i]]);
if(a[i] > 0) {
d[i][1][a[i] - 1] = d[i - 1][0][a[i - 1]] + 1;
if(a[i - 1] > 0)
d[i][1][a[i] - 1] = min(d[i - 1][0][a[i - 1] - 1] + 1, d[i][1][a[i] - 1]);
}
d[i][0][a[i]] = d[i - 1][1][a[i - 1]];
if(a[i - 1] > 0)
d[i][0][a[i]] = min(d[i - 1][1][a[i - 1] - 1], d[i][1][a[i]]);
if(a[i] > 0){
d[i][0][a[i] - 1] = d[i - 1][0][a[i - 1]];
if(a[i - 1] > 0)
d[i][0][a[i] - 1] = min(d[i][0][a[i] - 1], d[i - 1][0][a[i - 1] - 1]);
}
}
cout << min(d[n][1][a[n]], (a[n] > 0) ? d[n][1][a[n] - 1] : 999999);
return 0;
}
标签:begin,涂过,end,min,题解,small,CF1849D,cases
From: https://www.cnblogs.com/anjack511/p/18008941/solution-CF1849-D