HDU 2577（dp46）

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int dp[105][2]; char str[105]; int main() { int num; int i; scanf("%d\n",&num); while(num--) { gets(str); int len=strlen(str); memset(dp,0,sizeof(dp)); dp[0][1]=1; for(i=0;i<len;i++) { if(str[i]>='a'&&str[i]<='z') { dp[i+1][0]=min(dp[i][0]+1,dp[i][1]+2); dp[i+1][1]=min(dp[i][0]+2,dp[i][1]+2); } else { dp[i+1][0]=min(dp[i][0]+2,dp[i][1]+2); dp[i+1][1]=min(dp[i][0]+2,dp[i][1]+1); } } printf("%d\n",min(dp[len][0],dp[len][1]+1)); } return 0; }