公式

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

投稿日時:
最終更新: