题意：
打字游戏，求所按的最少次数。给出一个串，其中有大小写，大写需要按下cap键切换到大写，或者在小写状态下按shift+键，这样算两次，打小写时则相反。注意：在打完所有字后，如果cap键是开着的，要关它，也就是要算多一次。
思路：
DP，根据每个字符打完后cap键盘是开着的还是关着的，最后dp[最后一个字符][关着的]为答案。规模降低到1个字符，每次考虑增加一个字符，打这个字符有两种选择，从上一个字符打完后的cap键关/开的两种状态来按下此字符，按完此字符后考虑使cap键开着或者关掉。
dp[当前字符][关着的]= 可从两种途径而来（取最小即可）：（1）dp[上一个字符][关着的] （2）dp[上一个字符][开着的]
dp[当前字符][开着的]= 同上。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
using namespace std;
const int N=;
char str[N];
int dp1[N], dp2[N]; int cal(int len)
{ dp2[]=; //亮
for(int i=; i<=len; i++)
{
if( str[i]<='Z' ) //大写
{
dp1[i]=min(dp1[i-]+, dp2[i-]+);
dp2[i]=min(dp1[i-]+, dp2[i-]+);
}
else //小写
{ dp1[i]=min(dp1[i-]+, dp2[i-]+);
dp2[i]=min(dp1[i-]+, dp2[i-]+);
}
}
return min(dp1[len],dp2[len]+);
} int main()
{
//freopen("input.txt", "r", stdin);
int t;
cin>>t;
while(t--)
{
memset(dp1,,sizeof(dp1));
memset(dp2,,sizeof(dp2));
scanf("%s",str+);
cout<<cal(strlen(str+))<<endl;
}
return ;
}
AC代码