Codeforces 180C Letter：dp

题目链接：http://codeforces.com/problemset/problem/180/C

题意：

　　给你一个字符串s，长度为n。

　　让你将这个字符串变成“前面一段都是大写字母，后面一段都是小写字母”的形式。

　　（也可以全是大写或全是小写）

　　问你最少改动几个字符。

题解：

　　表示状态：

　　　　dp[i][0/1] = min changes

　　　　表示考虑到第i个字符，s[i]改成了大写(1)或小写(0)时的最小代价

　　找出答案：

　　　　ans = min(dp[n][0], dp[n][1])

　　如何转移：

　　　　dp[i][1] = dp[i-1][1] + is_lower(s[i])

　　　　dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + is_upper(s[i])

　　边界条件：

　　　　dp[i][0] = dp[i][1] = 0

AC Code:

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #define MAX_N 100005
 5 
 6 using namespace std;
 7 
 8 int n;
 9 int dp[MAX_N][2];
10 char s[MAX_N];
11 
12 int is_lower(char c)
13 {
14     return ('a'<=c && c<='z') ? 1 : 0;
15 }
16 
17 int is_upper(char c)
18 {
19     return ('A'<=c && c<='Z') ? 1 : 0;
20 }
21 
22 int main()
23 {
24     scanf("%s",s+1);
25     n=strlen(s+1);
26     memset(dp,0,sizeof(dp));
27     for(int i=1;i<=n;i++)
28     {
29         dp[i][1]=dp[i-1][1]+is_lower(s[i]);
30         dp[i][0]=min(dp[i-1][0],dp[i-1][1])+is_upper(s[i]);
31     }
32     cout<<min(dp[n][0],dp[n][1])<<endl;
33 }