去年天气旧亭台
题目背景
依旧是过往的天气,过往的楼台烟雨。时间悄悄流逝着,山河仍在,人却已不是过去的人……
题目描述
登上楼台,旧时满面沉灰的地板映入眼帘。
共有 $n$ 块地板,地板分为两类,第 $i$ 块地板的类别用 $c_i$ 表示,积灰程度用 $a_i$ 表示。注意 $c_i$ 为 $0$ 或 $1$。
现在要清理这些地板上的灰尘。每次操作中,你可以:
+ 选择两个下标 $i,j$,满足 $1\leq i\leq j\leq n$, $c_i=c_j$,且第 $i$ 块和第 $j$ 块地板上的灰尘均未被清理过;
+ 花费 $a_i+a_j$ 的能量清理第 $i$ 块到第 $j$ 块所有地板上的灰尘。
求清理完所有地板上的灰尘至少要多少能量。
输入格式
本题有多组测试数据。
第一行一个整数 $T$,表示测试数据组数。
对于每组测试数据:
- 第一行一个整数 $n$。
- 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。
- 第三行 $n$ 个整数 $c_1,c_2,\dots,c_n$。
输出格式
对于每组测试数据,一行一个整数表示最小能量。
样例输入 #1
```
2
6
1 1 4 5 1 4
1 0 0 1 0 1
8
3 1 4 1 5 9 2 6
1 0 1 0 1 0 1 0
```
样例输出 #1
```
5
13
```
提示
【样例 1 解释】
- 对于第一组数据,直接花费 $a_1+a_6=5$ 的能量清理所有灰尘。
- 对于第二组数据,先花费 $a_1+a_1=6$ 的能量清理第一个地板上的灰尘,再花费 $a_2+a_8=7$ 的能量清理剩余灰尘。
【数据规模与约定】
对于 $10\%$ 的数据,保证 $T\le 10$,$n\le 10$;
对于 $40\%$ 的数据,保证 $T\le 20$,$n\le 10^3$;
另有 $10\%$ 的数据,保证 $c_i=1$;
对于 $100\%$ 的数据,保证 $1 \le T \le 10^5$,$1 \le n,\sum n\le 2 \times 10^6$,$c_i \in \{0,1\}$,$1 \le a_i \le 10^9$。
----------
(动态规划) $O(n)$
洛谷5月月赛第二题,怎么说呢,还是比较简单的
考虑$\text{DP}$
设$f_i$为擦干净前i块地板的最小能量
显然可以推出状态转移方程:
$f_i = \max \limits _ {1 \le j \lt i, c_{j + 1} = c_i} \\{f_j + a_{j + 1} + a_i\\}$
复杂度$O(Tn ^ 2)$,会$\text{TLE}$
考虑优化
将式子拆开
$f_i = \max \limits _ {1 \le j \lt i, c_{j + 1} = c_i} \\{f_j + a_{j + 1}\\} + a_i$
显然,$max$部分和i无关,范围只增大不减小,所以可以用前缀和优化
复杂度$O(Tn) = O(\sum n) = 10 ^ 6$
$C++$ 代码
#include <iostream> #include <cstring> using namespace std; typedef long long LL; //注意long long const int N = 2000010; const LL INF = 0xffffffffff; int n, c[N], a[N]; LL f[N]; int main() { int T; scanf("%d", &T); while (T -- ) { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]); memset(f, 0x3f, sizeof f); f[0] = 0; LL min_v0 = INF, min_v1 = INF; //c_j + 1 = 0的最小值和c_j + 1 = 1的最小值 for (int i = 1; i <= n; i ++ ) //DP { if (!c[i]) min_v0 = min(min_v0, f[i - 1] + a[i]); else min_v1 = min(min_v1, f[i - 1] + a[i]); f[i] = min(f[i], (c[i] ? min_v1 : min_v0) + a[i]); } printf("%lld\n", f[n]); } return 0; }
标签:10,le,洛谷,int,灰尘,清理,地板,P9344,亭台 From: https://www.cnblogs.com/xyy-yyds/p/17418449.html