首页 > 试题广场 >

气球谜题

[编程题]气球谜题

热度指数：4218 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的 $n$ 个气球，摆放成一排，颜色仅为红、黄、蓝中的一种。小红想要让颜色相同的气球连续的摆放在一起，为了达成这个目标，她需要将气球重新染色。第 $i$ 个气球重新染成任意的颜色均需要 $t_i$ 秒，询问需要消耗的最少时间是多少呢。

输入描述:

第一行输入一个整数  代表气球数量。
第二行输入一个长度为  的、仅由  构成的字符串代表气球的初始颜色。其中， 分别代表初始颜色为红、黄、蓝。
第三行输入  个整数  代表气球重新染色需要的时间。

输出描述:

在一行上输出一个整数，代表最少需要的染色时间。

示例1

输入

5
00000
1 2 3 4 5

输出

说明

由于初始时全部气球颜色都是一样的，所以不需要重新进行染色。

示例2

输入

6
210102
1 1 4 5 1 4

输出

说明

其中一种最优的染色方案是将气球染色为  ，花费  。

示例3

输入

6
001012
1 1 4 5 1 4

输出

说明

其中一种最优的染色方案是将气球染色为  ，花费  。

算法知识视频讲解

Yves___

发表于 2024-12-08 21:43:59

D题的暴力优化：https://ac.nowcoder.com/acm/contest/97443/D 我去后面有点急了就没写出来。发现题解是dp，对于我这种蒟蒻来说还是很难写的。考虑暴力，令a，b，c分别是把大区间染成0，1，2的前缀和。假设这里把大区间分别染色为 0 1 2，枚举i和j为0和1 展开全文

Gooby114514

发表于 2024-12-09 11:16:51

D 气球谜题官方题解是DP做法，我们这里使用前缀和来做。由于最后的颜色排列是的全排列之一，所以我们也是枚举全排列，然后对于每一种排列进行枚举，具体方式如下：设当前的排列的颜色为。定义前缀和数组表示将前个气球全部变成颜色所需的时间，这个递推就可以解决，具体看代码。可以将最展开全文

Gnomeshgh112

发表于 2025-03-26 10:08:18

所有的解空间中，一共存在15中状态，每一种状态满足无后效性的性质，可以用动态规划来维护这15种状态，得到最优解。详细状态可见代码注释 #include <bits/stdc++.h> using namespace std; long long Min(long long a, lon 展开全文

蓝乐

发表于 2025-04-15 10:32:46

感谢大佬提供的思路，使用动态规划管理共15种状态，实际上每种状态的前置状态最多会有2种，理解了这一点状态转移方程就不难得出了 const rl = require("readline").createInterface({ input: process.stdin }); var 展开全文

小鹰划船不用桨

发表于 2025-04-11 12:52:00

def solve(n, a_str, t_list): a = list(map(int, a_str)) # 0/1/2 t = t_list # 预处理：计算前缀和 s[0], s[1], s[2] s = [[0] * (n + 1) for _ in r 展开全文

番禺小韭菜

发表于 2025-03-03 21:09:18

#include <algorithm> #include <climits> #include <iostream> #include <vector> using namespace std; int main() { int n; 展开全文

牛客856751393号

发表于 2025-03-05 15:51:52

【Python3】输出和C++版一致，但提交不通过，怀疑是系统问题。纯纯浪费我时间。末尾附赠一个测试用例。 from itertools import permutations n = int(input()) s = input() t = list(map(int, input().split 展开全文

zy还能再战

发表于 2025-03-27 10:01:45

#牛客春招刷题训练营# + 链接假定染色后的气球形如 xxxyyyzzz ，三个区间的右端点分别为i,j,n用 s(x,i) 表示前i个气球中所有原本是x色的染色费用和则有 cost=(s(y,i)+s(z,i))+((s(x,j)-s(x,i))+(s(z,j)-s(z,i)))+((s(x,n) 展开全文

苦闷的芒果在看数据

发表于 2025-12-10 11:31:50

import sysfrom itertools import permutationswhile True: try: n = int(input()) s = input() val = list(map(int,input().split())) 展开全文

王觊玮

发表于 2025-03-23 17:00:46

#include <algorithm> #include <cstdio> #include <iostream> #include <limits> #include "vector" using namespace std; 展开全文

问题信息

动态规划

难度：

9条回答 164收藏 512浏览

气球谜题

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题