题目链接：HDOJ 2577
题意：打出所给的字符串，大小写都有，并且最终Caps Lock 要关闭，求最少的按键数
题解：简单的dp方程，考虑Caps Lock on 和in的情况dp就可
代码：
#include<cstdio> #include<queue> #include<cstring> #include<string> #include<stack> using namespace std; #define M(a) memset(a,0,sizeof(a)) #define Max(a,b) ((a>b)?a:b) #define Min(a,b) ((a<b)?a:b) #define debug 0 const int maxn = 100 + 5; char str[maxn]; int word[maxn]; int dp[maxn][2]; void Do() { int len = strlen(str); for (int i = 1; i <= len; i++) if (isupper(str[i - 1])) //判断大小写 word[i] = 1; int num; if (word[1]) //初始化第一个字符type { dp[1][0] = 2; //dp[i][0]表示在Caps Lock关的状态情况打出第i个字符的最优解 dp[1][1] = 2; //dp[i][1]表示在Caps Lock开的状态情况打出第i个字符的最优解 } else { dp[1][0] = 1; dp[1][1] = 3; } for (int i = 2; i <= len; i++) { if (word[i]) { dp[i][0] = Min(dp[i - 1][0] + 2, dp[i - 1][1] + 3);//注意上一状态Caps Lock要先转Caps Lock再type dp[i][1] = Min(dp[i - 1][0] + 2, dp[i - 1][1] + 1); } else { dp[i][0] = Min(dp[i - 1][0] + 1, dp[i - 1][1] + 2); dp[i][1] = Min(dp[i - 1][0] + 3, dp[i - 1][1] + 2); } } printf("%d\n", Min(dp[len][0], dp[len][1] + 1));//最终Caps Lock要关闭 } int main() { #if debug freopen("in.txt", "r", stdin); #endif//debug int T; while (~scanf("%d", &T)) { while (T--) { M(dp); M(word); scanf("%s", str); Do(); } } return 0; }
