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: