首页 > 代码库 > Codeforces 180C. Letter
Codeforces 180C. Letter
题目链接:http://codeforces.com/problemset/problem/180/C
题意:
给你一个仅包含大写字母和小写字母的字符串,你可以将让小写字母转化为大写字母,大写字母转化为小写字母,求最好的操作步数使得最后的字符串左边全是大写字母,右边全是小写字母.
思路:
有点像是树状DP,把每个字母看成一个节点,后一个字母为前一个字母的父节点.给予每个节点两种状态:
状态一(dplow[i]) : 当字符串长度为 i 时,第 i 个字母为小写,得到符合条件的字符串的最少操作步数.
状态二(dpsup[i]) : 当字符串长度为 i 时,第 i 个字母为大写,得到符合条件的字符串的最少操作步数.
那么最后的答案取最后一个字母的两个状态中值小的那么就好了, 接下来分析下状态转移方程:
如果第 i 个字母为小写:
对于其状态一 : 不需要转化,当前节点本身为小写.因为当前状态可以由其子节点的状态一和状态二转移而来,所以只要取其中比较小的就好了,DP转移方程:
dplow[i] = min ( dplow[i - 1], dpsup[ i - 1]);
对于其状态二 : 转化完成后,当前节点为大写,那么当前状态只能由其子节点的状态二转移而来.所以当前的值为其子节点状态二的值加 1,DP转移方程为:
dpsup[i] = dpsup[ i - 1] + 1;
如果第 i 个字母为大写:
对于其状态一 : 转化为小写之后, 当前的状态可以由其子节点的状态一和状态二转移而来,所以当前值为其子节点两个状态值比较小的那个加 1,DP转移方程为:
dplow[i] = min ( dplow[i - 1], dpsup[ i - 1]) + 1;
对于其状态二 : 不需要转化,当前状态只能由其子节点的状态二转移而来.所以当前值就是其子节点状态二的值,DP转移方程为:
dpsup[i] = dpsup[i - 1];
至此,状态转移就分析完成了.实现上,由于父节点只和其子节点的状态有关,所以用两个变量就好了.
代码:
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 const int MAXN = 100000; 5 char s[MAXN + 3]; 6 7 void DFS(int k, int &tolow, int &tosup) { 8 if(k == 0) { isupper(s[k]) ? tolow = 1 : tosup = 1; return ; } 9 DFS(k - 1, tolow, tosup); tolow = min(tolow, tosup);10 isupper(s[k]) ? tolow++ : tosup ++;11 }12 13 int main() {14 ios_base::sync_with_stdio(0); cin.tie(0); cin >> s;15 int len = strlen(s), low = 0, sup = 0;16 DFS(len - 1, low, sup);17 cout << min(low, sup) << endl;18 return 0;19 }
Codeforces 180C. Letter