首页 > 其他分享 >洛谷 P9344. 去年天气旧亭台

洛谷 P9344. 去年天气旧亭台

时间:2023-05-21 12:33:08浏览次数:38  
标签:10 le 洛谷 int 灰尘 清理 地板 P9344 亭台

去年天气旧亭台

题目背景

依旧是过往的天气,过往的楼台烟雨。时间悄悄流逝着,山河仍在,人却已不是过去的人……

题目描述

登上楼台,旧时满面沉灰的地板映入眼帘。

共有 $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

相关文章

  • 洛谷 P9248 - [集训队互测 2018] 完美的集合
    显然,如果选择的\(k\)个“合法集合”固定了,那么可以放置装置的点如果存在,那么必然形成一个连通块,也就是说,答案等于所有合法方案中,可以放置装置的点形成的连通块个数之和。而根据点减边的套路,这等价于,枚举每个点,计算有多少种方案满足可以在其放置装置,再枚举每条边,计算有多少种方案......
  • 洛谷颜色对照表
    $$\def\arraystretch{1.2}\begin{array}{|c|l|l||c|l|l|}\hline颜色名称&十六进制编码&\text{RGB对应值}&颜色名称&十六进制编码&\text{RGB对应值}\\\hline\color{#52C41A}\text{AC绿}&\text{52C41A}&\text{(82,196,26)}&\color{#FE4C......
  • 洛谷 P8978 「DTOI-4」中位数
    首先考虑二分答案,把原序列变成01序列。那么问题就相当于转换成判断能否在\(k\)次操作内,将序列变成全\(1\)。由于每次操作一定可以做到把\(1\)的个数\(n\)变成\(n'=2n-1\)。因此可以得知操作一定是\(\logn\)级别的。但是这个问题仍然不太好做,很多贪心都是假的。考虑最......
  • 洛谷 P7999 [WFOI - 01] 翻转序列(requese)
    洛谷传送门注意到如果\(n\)足够小,可以过\(n^2\)。选\(x=3\)(这样做的好处是能交换两个相邻元素),每次把值为\(i\)的元素挪到\(i\),注意到我们不关心其他元素,所以翻转\([l,r]\)的效果可以看成是交换\(p_l,p_r\)。于是先跳大步,再跳小步。可以过\(n\le100\),拿到50分......
  • 洛谷 P4544 [USACO10NOV]Buying Feed G - 题解
    https://www.luogu.com.cn/problem/P4544感觉是很没意思的DP+DS优化,以前做过几道更难的题:https://codeforces.com/contest/1788/problem/Ehttps://atcoder.jp/contests/abc288/tasks/abc288_f这种题只要是让我写总是能把代码整的伤痕累累(逃第一眼:我艹不就是一个sbDP吗......
  • 机器分配 P2066 洛谷
    #dp#背包求方案#分组背包#字典序#T3机器分配P2066机器分配-洛谷|计算机科学教育新生态(luogu.com.cn)题目描述总公司拥有高效设备M台,准备分给下属的N个分公司。各分公司若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到的盈利最大?求出......
  • 洛谷 P5488 差分与前缀和
    洛谷传送门看起来很毒瘤,但是推出贡献系数后就是一个朴素的卷积了。首先考虑前缀和。考虑\(j\(j\lei)\)的\(a_j\)贡献到\(i\)的过程,是找到\(j=p_0\lep_1\le\cdots\lep_k=i\)的方案数。令\(x_i=p_i-p_{i-1}\),即求\(x_i\ge0,\sum\limits_{i=1}^kx_i......
  • 洛谷 P3321 [SDOI2015] 序列统计
    洛谷传送门感觉挺综合的一道题。考虑朴素dp,\(\forallx\inS,f_{i+1,jx\bmodm}\getsf_{i,j}\)。复杂度\(O(nm^2)\)。显然可以矩乘优化至\(O(m^3\logn)\),但是不能通过。如果转移式中是加法而不是乘法,那很容易卷积优化。接下来是一个很重要的套路:化乘为加。实数......
  • 洛谷 P8492 - [IOI2022] 无线电信号塔
    想到将最优化问题转化为数点问题的一步了,但是因为转化的姿势不太好导致我的数点不太能用特别简洁的数据结构维护,最后只好看题解(考虑先解决单组询问的问题,对于每个点\(i\),我们找出它左边最近的\(h_l\leh_i-D\)的点\(l\),和它右边最近的\(h_r\leh_i-D\)的点\(r\),然后新建一......
  • 洛谷 P8367 - [LNOI2022] 盒(组合数学)
    设\(a\)数组的前缀和为\(s_i\),\(b\)数组的前缀和为\(t_i\),那么根据模拟费用流或者贪心的思想,每一条边经过的次数即为\(|s_i-t_i|\),因此非常trivial的做法是转换贡献体,枚举每种方案下每条边被经过的次数,然后乘以\(w_i\)求和,具体来说:\[ans=\sum\limits_{i=1}^{n-1}\sum\l......