题目分析:参考了别人的思想!!!,为啥自己想半天都没想出这么好的方法 .
数组on[i]代表到第i个字母时,大写键是开着时输入字母,所需的最小按键次数;
数组off[i]代表大写键时关着时 ,到字母i,所需的按键最小次数;
很明显有:
如果s[i]是大写字母
{
on[i]=min(on[i-1]+1,off[i-1]+2);
off[i]=min(on[i-1]+2,off[i-1]+2);
}
如果s[i]为小写字母
{
on[i]=min(on[i-1]+2,off[i-1]+2);
off[i]=min(on[i-1]+2,off[i-1]+1);
}
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
bool inline is_upper(char x)
{
if('A'<=x&&x<='Z')
return true;
else
return false;
}
int main()
{
int t;
scanf("%d",&t);
getchar();
while(t--)
{
char s[120];
int on[120];//在大写是开着时,到第i个字母,所需要的最小按键次数
int off[120];//在大写是关着的时,到第i个字母,所需的最小按键次数
gets(s);
int len=strlen(s);
if(is_upper(s[0]))
{
on[0]=2;
off[0]=2;
}
else
{
on[0]=2;
off[0]=1;
}
for(int i=1;i<len;i++)
{
if(is_upper(s[i]))
{
on[i]=min(on[i-1]+1,off[i-1]+2);
off[i]=min(on[i-1]+2,off[i-1]+2);
}
else
{
on[i]=min(on[i-1]+2,off[i-1]+2);
off[i]=min(on[i-1]+2,off[i-1]+1);
}
}
printf("%d\n",off[len-1]);
}
system("pause");
return 0;
}