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
