拿到这个题，我们先来读一遍 看这里
英文不好，放弃
这道题的大意就是给你一个字符串，求打出它最少需要按多少次键盘
那么有以下几种可能：
1、caps lock锁定，输出大写
2、caps lock未锁定、按一次shift，输出一个大写
3、caps lock未锁定，输出小写
还有最坑的一项！！！caps lock锁定时按shift可以输出小写！！！（我当时被坑了好久......）
很明显的dp（据说模拟也可以）
接下来我们就开始愉快地推转移方程啦
根据我们之前写的可能性，可以写出以下几个式子
dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1);
dp[i][1]=min(dp[i-1][1],dp[i-1][0]+1);
大写时
dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1);
dp[i][1]=dp[i-1][1]+1;
小写时
其中i是字符串下标，0/1是状态（是否是大写）
再接下来。。。好像就没啦？
AC代码献上（写的这么烂就别抄了嘛）
#include<bits/stdc++.h> using namespace std; string a; int dp[105][2]; int main() { int T; cin>>T; while(T--) { cin>>a; int la=a.size(); for(int i=0;i<la;i++) { dp[i][0]=0; dp[i][1]=1; } if(a[0]>=‘A‘&&a[0]<=‘Z‘) dp[0][0]=1,dp[0][1]=1; for(int i=1;i<la;i++) { if(a[i]>=‘A‘&&a[i]<=‘Z‘) { dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1); dp[i][1]=min(dp[i-1][1],dp[i-1][0]+1); } if(a[i]>=‘a‘&&a[i]<=‘z‘) { dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1); dp[i][1]=dp[i-1][1]+1; } } cout<<min(dp[la-1][0],dp[la-1][1]+1)+la<<endl; } return 0; }
蒟蒻进阶第一步——dp 未完待续......
原文：https://www.cnblogs.com/ylq-juruo/p/11962579.html