题目链接
题意:
给你一些字符串a~z||A~Z，然后我们按键最少能把他们都打出来，
如果开始Cap大写灯是灭的，我们需要打A的话，可以按下cap键，
然后再按a，需要两步，但是这下状态变为了大写灯亮，
当然我们也可以按下shift，再按下a，需要两步，但是这下状态就变成了大写灯灭。
题目要求的是，把这些字母打出来需要的最小按键数目。
有一点需要注意，按键完成之后需要使cap键关闭。
思路:
很明显这个题是针对cap按键的亮和灭两个状态来的,那么我们就需要去讨论
Cap按键的亮和灭的两种状态.那么有 dp[i][0]表示打完第i个字母Cap灭的
最小按键数目,dp[i][1]表示打完第i个字母Cap亮的最小按键数目,很容易得到
转移方程:（需要注意的是Cap亮是 shift+a可打印小写,Cap灭时shift+a打印大写字母A）;
#include<bits/stdc++.h> using namespace std; int dp[111][2]; char s[111]; int t; int main() { cin>>t; while(t--) { memset(dp,0,sizeof(dp)); scanf("%s",s+1); int len=strlen(s+1); dp[0][0]=0; dp[0][1]=1; for(int i=1;i<=len;i++) { if(s[i]>='A'&&s[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]++;//将cap关闭 printf("%d\n",min(dp[len][0],dp[len][1])); } return 0; }
Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
