看到本题，很容易想到贪心，对每一段相同的子串计算最小代价。但这种思路的评测结果显示有 \(3\) 个测试点 WA 了，因此解法错误。既然贪心行不通，我们不妨使用 dp，对每一位进行分类讨论并求最小耗时。
设 \(dp_{i,j}\) 表示 Capslock 状态为 \(j\) 时（\(j\) 为 \(0\) 或\(1\)，\(0\) 表示熄灯，\(1\) 表示亮灯），前 \(i\) 位的最小耗时，接下来具体分析状态转移方程：
记 \(s_i\) 表示 \(s\) 中下标为 \(i\) 的字符。
- \(s_i = s_{i - 1}\)
这种情况下有如下状态转移方程：
- 若 \(s_i\) 为 A，则有
- 若 \(s_i\) 为 a，则有
- \(s_i \ne s_{i - 1}\)
推导过程同理，这里略过。
总结
这些式子看起来很长，其实理解起来并不难：先看状态是否一致，不一致则加上 \(z\)，然后再看只按 a 是否为需要的字母，如果不是则加上 \(y\)，否则加上 \(x\)。
具体实现如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
int x,y,z,len,l,nw;
int ans;
int dp[1000001][2];
char s[1000001];
signed main()
{
cin >> x >> y >> z;
cin >> s;
len = 1;
if( s[0] == 'a' )
{
dp[0][0] = x;
dp[0][1] = z + y;
}
else
{
dp[0][0] = y;
dp[0][1] = z + x;
}
l = strlen(s);
for( int i = 1 ; i < l ; i ++ )
{
if( s[i] == s[i - 1] )
{
if( s[i] == 'A' )
{
dp[i][0] = min( dp[i - 1][0] + y , dp[i - 1][1] + z + y );
dp[i][1] = min( dp[i - 1][0] + z + x , dp[i - 1][1] + x );
}
else
{
dp[i][0] = min( dp[i - 1][0] + x , dp[i - 1][1] + z + x );
dp[i][1] = min( dp[i - 1][0] + z + y , dp[i - 1][1] + y );
}
}
else
{
if( s[i - 1] == 'A' )
{
dp[i][0] = min( dp[i - 1][0] + x , dp[i - 1][1] + x + z );
dp[i][1] = min( dp[i - 1][0] + z + y , dp[i - 1][1] + y );
}
else
{
dp[i][0] = min( dp[i - 1][0] + y , dp[i - 1][1] + z + y );
dp[i][1] = min( dp[i - 1][0] + z + x , dp[i - 1][1] + x );
}
}
}
cout << min( dp[l - 1][0] , dp[l - 1][1] );
return 0;
}