公式
D - Shift vs. CapsLock 解説 by m_99
\(\mathrm{dp}_{i,j}\) を「 \(i\) 文字目まで入力した時点で CapsLock キーのランプが \(j=0\) ならばOFF、\(j=1\) ならばONである状態にするために必要な時間の最小値」として動的計画法を行います。
遷移として以下の \(4\) 種類を考えれば良いです(次に入力するべき文字と合致しないものは弾いてください)。
- \(X\) 秒かけて a キーのみを押す
- \(Y\) 秒かけて Shift キーと a キーを同時に押す
- \(Z+X\) 秒かけて CapsLock キーを押した上で a キーのみを押す
- \(Z+Y\) 秒かけて CapsLock キーを押した上で Shift キーと a キーを同時に押す
実装例(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;
}
投稿日時:
最終更新: