京东20190824笔试

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;
}