HDU 2577 How to Type DP也可以模拟

http://acm.hdu.edu.cn/showproblem.php pid=2577

大意：

大家都打过字吧，现在有个有趣的问题：给你一串字符串，有大写有小写，要求你按键次数最少来输出它，输出按键次数。

大写字母可以通过caps lock 也可以用shift得到，小写也是。

但是起始状态和最后caps lock都是不锁定的。

求最少的按键次数。

思路：

不用DP的方法：

当有连续的大写或者小写用caps lock 键，否则用shift。

#include
  
   
#include
   
     const int MAXN=110; int main() { int T; scanf("%d",&T); while(T--) { char a[MAXN]; scanf("%s",a); int len=strlen(a); bool capslock=false; int cnt=0; for(int i=0;i
    
     = 'A' && a[i] <= 'Z') { if(capslock==false) cnt++; //shift or capslock if(a[i+1]>= 'A' && a[i+1] <= 'Z') capslock=true; cnt++; } else { if(capslock==true) cnt++; //shift or capslock if(a[i+1]>= 'a' && a[i+1] <= 'z' ||a[i+1]=='\0') //a[i+1]=='\0'必须加，这也就是模拟wa原因 capslock=false; cnt++; } } if(capslock) cnt++; printf("%d\n",cnt); } return 0; }
    
   
  

DP的方法

设lock[i]为敲完第i个之后为锁定状态，而notlock[i]为敲完第i个之后为没有锁定状态

则分大小写讨论：

a[i]若为大写：

lock[i]=min(lock[i-1]+1,notlock[i-1]+2);
notlock[i]=min(lock[i-1]+2,notlock[i-1]+2);

否则：

lock[i]=min(lock[i-1]+2,notlock[i-1]+2);
notlock[i]=min(lock[i-1]+2,notlock[i-1]+1);

至于怎么来的，你敲一下键盘你就懂了

还有就是最后要变成没有锁定状态。。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; const int MAXN=110; int main() { int T; scanf("%d",&T); while(T--) { char a[MAXN]; int lock[MAXN]={0}; int notlock[MAXN]={0}; scanf("%s",a); int len=strlen(a); if(isupper(a[0])) { lock[0]=2; notlock[0]=2; } else { lock[0]=2; notlock[0]=1; } for(int i=1;i