How to Type

3PiratesHDUacmHDUACMSample Output
888HintThe string “Pirates”, can type this way, Shift, p, i, r, a, t, e, s, the answer is 8.The string “HDUacm”, can type this way, Caps lock, h, d, u, Caps lock, a, c, m, the answer is 8The string "HDUACM", can type this way Caps lock h, d, u, a, c, m, Caps lock, the answer is 8思路：dpa與dpb數(shù)組分別表示cap鍵開(kāi)關(guān)狀態(tài)，在完成第i個(gè)字母的最少步驟有兩種可能，在cap開(kāi)和關(guān)狀態(tài)，在第i-1個(gè)字母完成時(shí)，有兩種可能，一種是cap鍵開(kāi)，一種是關(guān)，每次取i-1狀態(tài)步驟的最小值，最后比較兩種狀態(tài)下，哪一種步驟最少。
 
#include<stdio.h>#include<string.h>char str[110];int dpa[110],dpb[110]; //dpa[110]表示燈亮，dpb[110]表示燈滅 int Min(int a, int b) {	return a > b ? b : a; }int main() {	int t,i;	scanf("%d",&t);	getchar();	dpa[0] = 1;	dpb[0] = 0;	while(t--) {		scanf("%s",str + 1);		for(i = 1; str[i]; i++) {			if(str[i] >= 'a' && str[i] <= 'z') {				dpa[i] = Min(dpa[i-1] + 2, dpb[i-1] + 2);//如果燈亮，按shift+字母，燈滅，按字母+cap 				dpb[i] = Min(dpa[i-1] + 2, dpb[i-1] + 1);//如果燈亮，按cap+字母，燈滅，按字母 			}			else if(str[i] >= 'A' && str[i] <= 'Z') {				 dpa[i] = Min(dpa[i-1] + 1, dpb[i-1] + 2);//如果燈亮，按字母，燈滅，按cap+字母 				 dpb[i] = Min(dpa[i-1] + 2, dpb[i-1] + 2);//如果燈亮，按字母+cap，燈滅，按shift字母 			}		}		printf("%d/n",Min(dpa[i-1] +1, dpb[i-1]));//燈亮著要關(guān)滅 	}	return 0;}