HDU2577 How to Type

原题链接:HDU2577

题目大意:Cathy 打字,有大写字母也有小写字母,她想尽可能少的敲键盘,可以按大写锁定键 $\rm Caps$,可以按$\rm shift$ 键来进行敲字 母。输出最少按键次数。注意,最后大写锁定键灯必须是灭的。

DP

状态表示:$f[i][0],f[i][1]$,已经敲完了前 $1$~$i$ 个字母,当前 $\rm Caps$ 状态为 $\rm off/on$,的最少按键次数

状态计算见代码,注意 $\rm Caps$ 处于 $\rm on$ 时,按 $\rm Shift$ 可以打出小写字母;最终以 $f[n][1]$ 结束则必须 $+1$ 关闭大写锁定。

答案:$min(f[n][0], f[n][1] + 1)$

 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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;

int T;
char str[N];
int f[N][2];

int main() {
	cin >> T;
	while (T--) {
		scanf("%s", str + 1);
		int n = strlen(str + 1);
		memset(f, 0x3f, sizeof f);
		f[0][0] = 0;
		f[0][1] = 1;
		for (int i = 1; i <= n; i++) {
			if (isupper(str[i])) { // 大写 
				f[i][0] = min(f[i - 1][1] + 2, f[i - 1][0] + 2);
				f[i][1] = min(f[i - 1][1] + 1, f[i - 1][0] + 2);
			} else { // 小写 
				f[i][0] = min(f[i - 1][0] + 1, f[i - 1][1] + 2);
				f[i][1] = min(f[i - 1][1] + 2, f[i - 1][0] + 2);
			}
		}
		printf("%d\n", min(f[n][0], f[n][1] + 1));
	}
	return 0;
}
updatedupdated2020-05-192020-05-19
加载评论
点击刷新