牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色，这个正方形的颜色将会被覆盖。牛牛的目标是在完成染色之后，每个红色R都比每个绿色G距离最左侧近。牛牛想知道他最少需要涂染几个正方形。
如样例所示: s = RGRGR
我们涂染之后变成RRRGG或RRRRR就满足要求了，涂染的个数都为2，没有涂染个数更少的方案了。
[编程题]红和绿
O(n)时间，O(n)空间动态规划解法
While True:
try:
s = input()
n = len(s)
#dp[i]: 使前i个正方形全红最少需要的染色数
dp = []
#计算dp[0]，即使所
展开全文
红绿颜色平衡点探寻求解问题. 牛牛有一些排成一行的正方形，每个正方形已经被染成红色或者绿色，牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色，这个正方形的颜色将会被覆盖，牛牛的目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近，牛牛想知道他最少需要涂染几个正方形.
展开全文
//第一眼看到这个题，就觉得会不会用动态规划，反正不会了就再用递归直接暴力解无所谓
//然后想动态策略，
//假设我前面三个值的最优解n已经存在，那我第四个值能不能用前边的最优解？（以小见大）
//当我第四个是G的时候，首先确定前三个最优解肯定是符合题目要求规律的，所以如果是G,那就啥都不变直接继承
展开全文
###这种动态更新的精髓在于，按照要求对于R从左边更新，但是记录这个更新次数的数组的维度需要比原字符串的维度大1，因为在最开始或者最后的0代表着开始，那么针对第一个字符元素，字符是[0]
但是记录的次数的这个数组就是[1]了。
###这里不能使用numpy库，否则可以使用arrR=np.zeros(
展开全文
colors = input()
n = len(colors)
allR = [0] * (n + 1) # 将i左侧全染成R最少需要的次数
allG = [0] * n # 将i及i右侧全染成G最少需要的次数
for i in range(1, n + 1):
if colors[i
展开全文
s = input()
n = []
#找R和G的分界处，统计每个分界处需要涂的数量，然和取最小的一个
for i in range(len(s)+1):
n.append(s[0:i].count('G') + s[i:].count('R'))
print(min(n))
str = input("")
# 以每个位置作为最后一个红色所在的位置，判断为i前面（[0, i-1]）有多少个绿色g_cnt，后面（[i+1, lens-1]）有多个红色r_cnt，i位置满足要求需要染色的总个数 = g_cnt + r_cnt
lens = len(str)
g_cnts =
展开全文
#include <iostream>
#include <string>
using namespace std;
int r[52], g[52];
int min(int a, int b){return a <b?a:b;}
int main() {
展开全文
问题信息
通过挑战的用户
-
2022-12-14 20:05:08 -
2022-11-15 10:59:21 -
2022-09-15 21:37:47
-
2022-09-11 15:41:32 -
2022-09-04 23:12:54
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
