题意:求输出字符串时按键个数的最小值。大小写转换时按的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; }