HDU - 2577 How to Type

题意：求打印这串字符串的最小的步数

思路：很容易想到用一维来表示状态，起初还想表示shift的状态，但后来发现不需要，只要把握大小写的状态就行了，那么就简单点了，状态的转移，0表示当前是小写的，1表示当前时大写的，所以用dp[i][2]表示前i个，状态为0或1时的最小值，最后如果是要回归到小写的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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;
}

HDU - 2577 How to Type,布布扣,bubuko.com

HDU - 2577 How to Type

原文：http://blog.csdn.net/u011345136/article/details/21114073