1.最优打字策略
#include <iostream> #include <cstring> #include <vector> #define INF 1000005 using namespace std; int dp[INF][2]; int main(){ int n; string s; while(cin >> n){ memset(dp,0,sizeof(dp)); cin >> s; //dp[i][j]表示输入第i位的字符,当前状态为j输入法时一共需要按多少次键(j=0为小写j=1为大写) dp[0][0] = isupper(s[0]) ? 2:1; dp[0][1] = 2; for(int i=1;i<n;i++){ if(isupper(s[i])){ dp[i][0] = min(dp[i-1][0]+2,dp[i-1][1]+2); dp[i][1] = min(dp[i-1][0]+2,dp[i-1][1]+1); } else{ dp[i][0] = min(dp[i-1][0]+1,dp[i-1][1]+2); dp[i][1] = min(dp[i-1][0]+2,dp[i-1][1]+2); } } cout << min(dp[n-1][0],dp[n-1][1]) << endl; } return 0; }
这道题和codeforce的http://codeforces.com/contest/180/problem/C很类似
代码:
#include <iostream> #include <cstring> #include <cctype> using namespace std; int dp[100100][2]; int main(){ string s; while(cin >> s){ int len = s.length(); memset(dp,0,sizeof(dp)); for(int i=0;i<len;i++){ if(isupper(s[i])){ dp[i][0] = min(dp[i-1][0]+1,dp[i-1][1]+1); dp[i][1] = dp[i-1][1]; } else{ dp[i][0] = min(dp[i-1][0],dp[i-1][1]); dp[i][1] = dp[i-1][1]+1; } } cout << min(dp[len-1][0],dp[len-1][1]) << endl; } return 0; }