题意：
有大写字母也有小写字母，她想尽可能少的敲键盘，可以按大写锁定键，可以按Shift键来进行敲字母
输出最少按键次数，注意，最后大写锁定键灯必须是灭的；
思路：把状态分为大写模式和小写模式进行dp
#include <cstdio> #include <map> #include <iostream> #include<cstring> #include<bits/stdc++.h> #define ll long long int #define M 6 using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const ll mod=1e9+7; int dp[107][2]; //0表示小写状态 1表示大写状态 int main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--){ string s; cin>>s; int len=s.size(); dp[0][0]=0; dp[0][1]=1; for(int i=1;i<=len;i++){ if(s[i-1]>=‘a‘&&s[i-1]<=‘z‘){ dp[i][0]=dp[i-1][0]+1; //如果是小写字母 自然是从小写状态+1最优 dp[i][1]=min(dp[i-1][1]+2,dp[i][0]+1); //大写状态则是由前一个大写状态用shift //或者由小写状态的最优情况转成大写 }else{ //同理 dp[i][1]=dp[i-1][1]+1; dp[i][0]=min(dp[i-1][0]+2,dp[i][1]+1); } } cout<<min(dp[len][0],dp[len][1]+1)<<endl; } }
原文：https://www.cnblogs.com/wmj6/p/10388968.html