题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2577
解题报告：有一个长度在100以内的字符串，并且这个字符串只有大写和小写字母组成，现在要把这些字符串用键盘输入到电脑中，一开始的时候大写锁定是关闭的，并且要求结束的时候也是关闭的，然后让你求输入这些字符串最少需要按多少次键盘（包括Cap Lock键和Shift键）
一个典型的dp题，定义一个一维数组就够了，然后dp[i]的含义的输入到第i个字符时需要按键的最少次数。然后递推公式如下：
dp[i] = min(dp[i],dp[j-1] + judge1(j,i));
dp[i] = min(dp[i],dp[j-1] + judge2(j,i));
两种输入方式分别是从第j个字符到第i个字符打开大写锁定来输入，另一种方式是关闭大写锁定来输入第j到i的字符。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<deque>
#include<map>
#include<queue>
#include<cstdlib>
using namespace std;
const int maxn = ;
char str[maxn];
int dp[maxn];
int judge1(int x,int y)
{
int sum = ;
for(int i = x;i <= y;++i)
if(str[i] >= 'A' && str[i] <= 'Z')
sum++;
else if(str[i] >= 'a' && str[i] <= 'z')
sum += ;
return sum;
}
int judge2(int x,int y)
{
int sum = ;
for(int i = x;i <= y;++i)
if(str[i] >= 'A' && str[i] <= 'Z')
sum += ;
else if(str[i] >= 'a' && str[i] <= 'z')
sum++;
return sum;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",str+);
int len = strlen(str+);
memset(dp,0x3f,sizeof(dp));
dp[] = ; //使0号为0，后面要-1，不用做特殊处理
for(int i = ;i <= len;++i)
for(int j = ;j <= i;++j)
{
dp[i] = min(dp[i],dp[j-] + judge1(j,i));
dp[i] = min(dp[i],dp[j-] + judge2(j,i));
}
printf("%d\n",dp[len]);
}
return ;
}