25573: 红蓝玫瑰

dp, greedy, http://cs101.openjudge.cn/practice/25573/

“玫瑰的红，容易受伤的梦，握在手中却流失于指缝，又落空”

有n (n<500000)支玫瑰从左到右排成一排，它们的颜色是红色或蓝色，红色玫瑰用R表示，蓝色玫瑰用B表示

作为魔法女巫的你，掌握两种魔法：

魔法1：对一支玫瑰施加颜色反转咒语

魔法2：对从左数前k支玫瑰同时施加颜色反转咒语（每次施法时的k值可以不同）

颜色反转咒语将使红玫瑰变成蓝玫瑰，蓝玫瑰变成红玫瑰

请你求出，最少使用多少次魔法，能使得这一排玫瑰全都变为红玫瑰

输入

一个字符串，由R和B组成

输出

一个整数，最少使用多少次魔法

样例输入

Sample Input1:
RRRRRBR

Sample Output1:
1

样例输出

Sample Input2:
RRRBBBRRRBBB

Sample Output2:
4

解释：先使用魔法2令k=12，得到BBBRRRBBBRRR，然后使用魔法2令k=9，得到RRRBBBRRRRRR，
然后使用魔法2令k=6，得到BBBRRRRRRRRR，然后使用魔法2令k=3，得到RRRRRRRRRRRR。
共使用了4次魔法

提示

tags: dp, greedy

来源：2022fall-cs101, gdr

25573: 红蓝玫瑰，有点像蒋子轩23工学院推荐的CF那两个dp题目：698A-vacations，1195C-Basketball Exercise。

2022fall-cs101，姜鑫。

思路的关键是建了两个一维dp，一个是前n朵玫瑰全变红，记为Rn，一个是前n朵玫瑰全变蓝，记为Bn。如果n+1朵玫瑰是红色，R(n+1)=Rn,B(n+1)可以通过魔法一由前n朵全是蓝色的玫瑰变来，也可以通过魔法二由前n朵全是红色的玫瑰变来。所以B(n+1)=min(Rn,Bn)+1。如果n+1朵玫瑰是蓝色就反过来。最后对R1，B1赋个值就可以快乐dp了。

python

r=list(input())
n=len(r)
R=[0]*n
B=[0]*n
if r[0]=="R":R[0]=0;B[0]=1
else:R[0]=1;B[0]=0
for i in range(n-1):
    if r[i+1]=="R":
        R[i+1]=R[i]
        B[i+1]=min(R[i],B[i])+1
    else:
        R[i+1]=min(R[i],B[i])+1
        B[i+1]=B[i]
print(R[-1])

python

# 22-化院-余力圣, greedy

s = list(input()); n=len(s); ans=0; t=0
for i in range(n-1,-1,-1):
    b = ['B', 'R'][t%2]
    if s[i]==b and s[i-1]!=b: ans += 1
    if s[i]==b and s[i-1]==b: ans += 1; t+=1
print(ans)

python

#22-地空-罗浩宇，dp玫瑰简单易懂
s=input();n=len(s)
dp=[[0 for i in range(2)] for j in range(n)]

######dp[i][0/1]表示前i个考虑完之后，并且前i个都是R/B需要的最少次数

if s[0]=='R':
    dp[0][0],dp[0][1]=0,1
else:
    dp[0][0],dp[1][0]=1,0
for i in range(1, n):
    if s[i]=='R':
        dp[i][0],dp[i][1]=min(dp[i-1][0],dp[i-1][1]+2), min(dp[i-1][0],dp[i-1][1])+1
    else:
        dp[i][0],dp[i][1]=min(dp[i-1][0],dp[i-1][1])+1, min(dp[i-1][0]+2,dp[i-1][1])
print(dp[n-1][0])

python

#红蓝玫瑰  【黄昌浩 生命科学学院 22秋】

#载入输入。设置变量ans，记录使用的魔法总数。
roses = list(input())
ans = 0

#设置变量flag，记录“反转”状态。（重要）
#“反转”：剩余序列中全部花的颜色被魔法2反转。
#若flag为0，则未反转。序列中R对应R，B对应B。若flag为1，则反转。则序列中R和B实际上变成B和R。
flag = 0

#代码主体。从后往前遍历。
#若遍历到R（i.e.未反转的R或反转的B），直接删除。因为我们必定不用对序列末端的R施用任何魔法了。
#若遍历到B（i.e.未反转的B或反转的R），考虑是否只有一朵B。若只有一朵，用一次魔法1，将其变成R。故ans+=1后，
#直接删除。若不止一朵，则用魔法2将剩余全部花反转。反转后，由于最后一朵花变成了“R”，即将其删除。
#遍历完所有花，ans的值即是魔法的总数。
while roses:
    if roses[-1] == ['R', 'B'][flag]:
        roses.pop()
    else:
        if len(roses) > 1:
            if roses[-2] == ['R', 'B'][flag]:
                roses.pop()
                ans += 1
                continue
        roses.pop()
        ans += 1
        flag ^= 1
print(ans)

python

'''
greedy，从后往前遍历，看当前这个和他的前面那个，如果这两个相同，并且都需要变化，那就使用一次魔法2，
用magic来记录当前这个位置使用过的魔法2，方便后续判断；
如果这两个不同，也就是当前这个需要被改变，而前面那个不需要，那么就是用魔法1，改变当前这一个
'''

def judge(c,m):
    if c=="B":
        return m==1
    if c=="R":
        return m==0

s=input()
L=len(s)
cnt=0
magic=0

for i in range(L-1,-1,-1):
    if judge(s[i],magic)==True:
        continue
    if i>0 and s[i]==s[i-1]:
        magic = 1 - magic
    cnt += 1
print(cnt)

python

#21-元培-闫钰乔
roses = list(input())
n = len(roses)
dp = [[0,0] for _ in range(n)]
for i in range(n):
    if roses[i] == 'R':
        dp[i][0] = dp[i-1][0]
        dp[i][1] = min(dp[i-1][1],dp[i-1][0])+1
    else:
        dp[i][0] = min(dp[i-1][1],dp[i-1][0])+1
        dp[i][1] = dp[i-1][1]
print(dp[n-1][0])

25573: 红蓝玫瑰 ​

25573: 红蓝玫瑰