Official

D - Shift vs. CapsLock Editorial by en_translator


We perform a Dynamic Programming (DP) where \(\mathrm{dp}_{i,j}\) is the shortest duration required to type the first \(i\) characters, finishing with Caps Lock light off if \(j=0\) and on if \(j=1\).
It is sufficient to consider the following four transitions (skip those not yielding the desired character).

  • Spend \(X\) seconds to press only the ‘a’ key
  • Spend \(X\) seconds to press the Shift and ‘a’ key simultaneously
  • Spend \(Z+X\) seconds to press the Caps Lock key, then only ‘a’ key
  • Spend \(Z+Y\) seconds to press the Caps Lock key, then Shift and ‘a’ key simultaneously

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;

constexpr long long INF = 1000000000000000000;

int main() {
    
	long long X,Y,Z;
	cin>>X>>Y>>Z;
	
	string S;
	cin>>S;
	
	vector dp(S.size()+1,vector<long long>(2,INF));
	dp[0][0] = 0;
	
	for(int i=0;i<S.size();i++){
		int cur;
		if(S[i]=='a')cur = 0;
		else cur = 1;
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++){
				long long v = dp[i][j];
				if(j!=k)v += Z;
				if(cur==k)v += X;
				else v += Y;
				dp[i+1][k] = min(dp[i+1][k],v);
			}
		}		
	}
	
	cout<<min(dp[S.size()][0],dp[S.size()][1])<<endl;
	
	return 0;
}

posted:
last update: