补题 [ABC303D] Shift vs. CapsLock

题目描述

あなたのパソコンのキーボードには、a キー・Shift キー・CapsLock キーの $ 3 $ 種類のキーがあります。また、CapsLock キーにはランプが付いています。 初め、CapsLock キーのランプは OFF であり、パソコンの画面には空文字列が表示されています。

あなたは、以下の $ 3 $ 種類の操作のうち $ 1 $ つを選んで実行するということを $ 0 $ 回以上何度でも行うことができます。

  • $ X $ ミリ秒かけて a キーのみを押す。CapsLock キーのランプが OFF ならば画面の文字列の末尾に a が付け足され、ON ならば A が付け足される。
  • $ Y $ ミリ秒かけて Shift キーと a キーを同時に押す。CapsLock キーのランプが OFF ならば画面の文字列の末尾に A が付け足され、 ON ならば a が付け足される。
  • $ Z $ ミリ秒かけて CapsLock キーを押す。CapsLock キーのランプが OFF ならば ON に、ON ならば OFF に切り替わる。

A と a からなる文字列 $ S $ が与えられます。画面の文字列を $ S $ に一致させるのに必要な最短の時間は何ミリ秒かを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ X $ $ Y $ $ Z $ $ S $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

1
2
1 3 3
AAaA

样例输出 #1

1
9

样例 #2

样例输入 #2

1
2
1 1 100
aAaAaA

样例输出 #2

1
6

样例 #3

样例输入 #3

1
2
1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

样例输出 #3

1
40

提示

制約

  • $ 1\ \leq\ X,Y,Z\ \leq\ 10^9 $
  • $ X,Y,Z $ は整数
  • $ 1\ \leq\ |S|\ \leq\ 3\ \times\ 10^5 $
  • $ S $ は A と a からなる文字列

Sample Explanation 1

以下のように操作を行うと $ 9 $ ミリ秒で画面の文字列を AAaA に一致させられます。これが最短の時間です。 - $ Z(=3) $ ミリ秒かけて CapsLock キーを押す。CapsLock キーのランプが ON になる。 - $ X(=1) $ ミリ秒かけて a キーを押す。A が画面の文字列の末尾に付け足される。 - $ X(=1) $ ミリ秒かけて a キーを押す。A が画面の文字列の末尾に付け足される。 - $ Y(=3) $ ミリ秒かけて Shift キーと a キーを同時に押す。a が画面の文字列の末尾に付け足される。 - $ X(=1) $ ミリ秒かけて a キーを押す。A が画面の文字列の末尾に付け足される。

题解

题目解析

当时没做出来,白瞎我这几周一直做dp题目,当时我没看出来这是dp题,我当时想暴力做…

废话少说,开始题目解析.这是一道线性dp题,我们分析一下这道题,这个输入方式一共有三种情况:

  • 仅按下 a 键 X 毫秒。 如果 CapsLock 键灯熄灭，则在屏幕上的字符串末尾添加 a，如果灯亮，则添加 A。
  • 同时按下 Shift 和 a 键 Y 毫秒。 如果 CapsLock 键灯熄灭，则在屏幕上的字符串末尾添加 A，如果灯亮，则添加 a。
  • 按住 Caps Lock 键 Z 毫秒。 如果 CapsLock 键灯熄灭，它将打开，如果打开，它将关闭。

分析一下,输出a有四种情况:

  • 此时 CapsLock 键灯熄灭,直接按下 a 键 X 毫秒,之后CapsLock 键灯还是熄灭的.
  • 此时 CapsLock 键灯熄灭,按住 Caps Lock 键 Z 毫秒,之后同时按下 Shift 和 a 键 Y 毫秒,之后CapsLock 键灯是亮的.
  • 此时 CapsLock 键灯亮,按住 Caps Lock 键 Z 毫秒,之后按下 a 键 X 毫秒,之后CapsLock 键灯是熄灭的.
  • 此时 CapsLock 键灯亮,同时按下 Shift 和 a 键 Y 毫秒,之后CapsLock 键灯还是亮的

依据这个情况,同理我们也能得到输出A的四种情况.

利用这个,我们可以创建状态转移方程:

当i-th的位置是a的时候有这个方程

当i-th的位置是A的时候有这个方程

解释一下:

dp[i][0]的意思为经历前i个后,CapsLock 键灯灭的最少次数.

dp[i][1]的意思为经历前i个后,CapsLock 键灯亮的最少次数.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <string>
#include <algorithm>
#define endl "\n"
using namespace std;
typedef long long ll;
const int MAXN = 3e5+10;

ll dp[MAXN][2];

int main(){
	int x,y,z;
	string s;
	cin >> x >> y >> z;
	cin >> s;
	if(s[0] == 'a'){
		dp[0][0] = x;
		dp[0][1] = y + z;
	}else{
		dp[0][0] = y;
		dp[0][1] = z + x;
	}
	for(int i=1;i<s.size();i++){
		if(s[i] == 'a'){
			dp[i][0] = min(dp[i-1][0] + x,dp[i-1][1] + z + x);
			dp[i][1] = min(dp[i-1][0] + z + y,dp[i-1][1] + y);
		}else{
			dp[i][0] = min(dp[i-1][0] + y,dp[i-1][1] + z + y);
			dp[i][1] = min(dp[i-1][0] + z + x,dp[i-1][1] + x);
		}
	}
	cout<<min(dp[s.size()-1][0],dp[s.size()-1][1]);
	return 0;
}