HDU - 2577 How to Type

題意：求打印這串字符串的最小的步數

思路：很容易想到用一維來表示狀態，起初還想表示shift的狀態，但後來發現不需要，只要把握大小寫的狀態就行了，那麼就簡單點了，狀態的轉移，0表示當前是小寫的，1表示當前時大寫的，所以用dp[i][2]表示前i個，狀態為0或1時的最小值，最後如果是要回歸到小寫的

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 110;

char str[MAXN];
int dp[MAXN][2];

int main(){
	int t;
	scanf("%d",&t);
	while (t--){
		scanf("%s",str);
		int len = strlen(str);
		memset(dp,0,sizeof(dp));
		if (str[0] >= 'A' && str[0] <= 'Z'){
			dp[0][0] = 2;
			dp[0][1] = 2;
		}
		else {
			dp[0][0] = 1;
			dp[0][1] = 2;
		}
		for (int i = 1; i < len; i++){
			if (str[i] >= 'A' && str[i] <= 'Z'){
				dp[i][0] = min(dp[i-1][0]+2,dp[i-1][1]+2);
				dp[i][1] = dp[i-1][1] + 1;
			}
			else {
				dp[i][0] = dp[i-1][0] + 1;
				dp[i][1] = min(dp[i-1][1]+2,dp[i-1][0]+2);

			}
		}
		int ans = min(dp[len-1][0],dp[len-1][1]+1);
		printf("%d\n",ans);
	}	
	return 0;
}