题目转自hdu 2577，题目传送门

题目大意：

现给你n个区分大小写的字符串，大小写可用Caps Lock和shift切换（学过计算机的都知道）

但是有一点需要注意（shift是切换，若现在是大写锁定，用shift可切换成小写）

这道题一开始拿的时候，就觉得是n²的dp

但是，转移方程一直没想出来（耗时0.25h）

后来又仔细想想，发现是2n的dp

然后想了想，20min就切了

解题思路：

我们先将字符串做预处理，形成一个01字符串

像这个测试数据：

HELlowORLd

可以转换成这样：

1110001110

然后，就可以写转移方程了

如果目前的字符需要大写，就是这样：

dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1)+1;
dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1])+1;

dp[i][0]代表第i个字符，有大写锁定，dp[i][1]代表第i个字符，无大写锁定

若不需要大写，则是这样：

dp[i][0]=min(dp[i-1][1]+1,dp[i-1][0])+1;
dp[i][1]=min(dp[i-1][1]+1,dp[i-1][0]+1)+1;

（意思自己理解，暴怒蒟蒻在线虐人）

然后就很简单了，AC代码如下（码风清奇，请勿怪罪）

#include<bits/stdc++.h>
using namespace std;
char s[110];
int n,t[110],dp[110][2];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        memset(t,0,sizeof(t));
        scanf("%s",&s);
        int l=strlen(s);
        for(int i=0;i<l;i++) if(s[i]>=65 && s[i]<=90) t[i]=1;//预处理 
        dp[0][1]=2;
        if(t[0]==1) dp[0][0]=2;
        else dp[0][0]=1;//初始化 
        for(int i=1;i<l;i++)
        {
            if(t[i]==1)
            {
                dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1)+1;
                dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1])+1;
            }
            else 
            {
                dp[i][0]=min(dp[i-1][1]+1,dp[i-1][0])+1;
                dp[i][1]=min(dp[i-1][1]+1,dp[i-1][0]+1)+1;
            }//转移方程 
        }
        printf("%d\n",min(dp[l-1][0],dp[l-1][1]+1));//还需要比较 
    }
    return ~~(0-0);//装个13 
}

就这样，这道题就可以轻松AC了......

dp之旅，未完待续.......