hdu 2577 How to Type

题意：求输出字符串时按键个数的最小值。大小写转换时按的shift、caps也计算在内。

原来CapsLock亮的时候按shift是可以打小写字母!!!

/*

若灯亮，则直接按字母；若灯灭，则按字母再开灯

若灯亮，则要先按字母再关灯；若灯灭，则按shift+字母

*/

dp[i][j]表示第i个字符在caps灯为j状态时的输入步数。j=0表示灯灭。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

int dp[105][2];

int main()
{
    int n,len,ans;
    char str[105];
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str+1);
            len=strlen(str+1);
            memset(dp,0,sizeof(dp));
            dp[0][1]=1;
            for(int i=1;i<=len;i++)
            {
                if(str[i]>=‘A‘&&str[i]<=‘Z‘)
                {
                    dp[i][0]=min(dp[i-1][0]+2,dp[i-1][1]+2);
                    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]+2,dp[i-1][1]+2);
                }
            }
            dp[len][1]++;
            ans=min(dp[len][0],dp[len][1]);
            printf("%d\n",ans);
        }
    }
    return 0;
}

hdu 2577 How to Type

原文：http://blog.csdn.net/u012841845/article/details/18601887