Posted on 2010-11-28 21:56
小小菜鸟蛋 阅读(467)
评论(1) 编辑 收藏 引用 所属分类:
某蛋的解题报告
http://acm.hdu.edu.cn/showproblem.php?pid=2577本来以为直接暴力就可以的，没想到，原来CapsLock亮的时候按shift是可以打小写字母。。。没这么打字过。。。所以，此题明显dp。不过，我一开始想错了，只开了一个数组dp，后来看了一下别人的解题报告，原来是要开两个数组表示CapsLock键的开关两个状态下的最小按键数。
on[i] 表示按第 i 个字母时CapsLock键亮着
off[i] 表示按第 i 个字母时CapsLock键暗着
若s[i]为大写字母：on[i] = min(on[i-1] + 1, off[i-1] + 2) //若灯亮，则直接按字母；若灯灭，则按字母再开灯
off[i] = min(on[i-1] + 2, off[i-1] + 2) //若灯亮，则要先按字母再关灯；若灯灭，则按shift+字母
若s[i]为小写字母：on[i] = min(on[i-1] + 2, off[i-1] + 2)
off[i] = min(on[i-1] + 2, off[i-1] + 1)
注意初始化：初始状态时，CapsLock键是暗的。
s[0]为大写字母：on[0] = 2, off[0] = 2;
s[0]为小写字母：on[0] = 2, off[0] = 1;
01 #include <iostream>
02 #include <string>
03 #include <algorithm>
04 using namespace std;
05
06 const int N = 110;
07 int on[N], off[N];
08
09 bool IsUpperCase(char ch)
10 {
11 if (ch - 'A' < 26)
12 return true;
13 return false;
14 }
15
16 int main()
17 {
18 string str;
19 int t;
20 for (cin >> t; t; t--)
21 {
22 memset(on, 0, sizeof(on));
23 memset(off, 0, sizeof(off));
24 cin >> str;
25 int n = str.size();
26 if(IsUpperCase(str[0]))
27 on[0] = off[0] = 2; //on[0]是先开后按，off[0]是shift+字母
28 else
29 {
30 on[0] = 2; //先按后开
31 off[0] = 1; //直接按
32 }
33 for (int i = 1; i < n; i++)
34 {
35 if (IsUpperCase(str[i]))
36 {
37 on[i] = min(on[i-1]+1, off[i-1]+2);
38 off[i] = min(on[i-1]+2, off[i-1]+2);
39 }
40 else
41 {
42 on[i] = min(on[i-1]+2, off[i-1]+2);
43 off[i] = min(on[i-1]+2, off[i-1]+1);
44 }
45 }
46 on[n-1]++; //最后要把CapsLock给关掉
47
48 cout << min(on[n-1], off[n-1]) << endl;
49 }
50 }