Home » 国际竞赛 » Details

USACO 2019 December Contest, Gold Problem 3. Moortal Cowmbat

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月1日下午3:24

USACO 2019 December Contest, Gold Problem 3. Moortal Cowmbat

Bessie has been playing the popular fighting game Moortal Cowmbat for a long time now. However, the game developers have recently rolled out an update that is forcing Bessie to change her play style.

The game uses $M$ buttons labeled by the first $M$ lowercase letters ( $1 \leq M \leq 26$ ). Bessie's favorite combo of moves in the game is a length- $N$ string $S$ of button presses ( $1 \leq N \leq 10^{5}$ ). However, due to the most recent update, every combo must now be made from a series of "streaks", where a streak is defined as a series of the same button pressed at least $K$ times in a row ( $1 \leq K \leq N$ ). Bessie wants to modify her favorite combo to produce a new combo of the same length $N$ , but made from streaks of button presses to satisfy the change in rules.

It takes $a_{i j}$ days for Bessie to train herself to press button $j$ instead of button $i$ at any specific location in her combo (i.e. it costs $a_{i j}$ to change a single specific letter in $S$ from $i$ to $j$ ). Note that it might take less time to switch from using button $i$ to an intermediate button $k$ and then from button $k$ to button $j$ rather than from $i$ to $j$ directly (or more generally, there may be a path of changes starting with $i$ and ending with $j$ that gives the best overall cost for switching from button $i$ ultimately to button $j$ ).

Help Bessie determine the smallest possible number of days she needs to create a combo that supports the new requirements.

SCORING:

Test cases 2-4 satisfy $N \leq 1000, K \leq 50.$
Test cases 5-8 satisfy $N \leq 30, 000, K \leq 50.$

INPUT FORMAT (file cowmbat.in):

The first line of input contains $N$ , $M$ , and $K$ . The second line contains $S$ , and the final $M$ lines contain an $M \times M$ matrix of values $a_{i j}$ , where $a_{i j}$ is an integer in the range $0 \dots 1000$ and $a_{i i} = 0$ for all $i$ .

OUTPUT FORMAT (file cowmbat.out):

Output a single number, representing the minimum number of days Bessie needs to change her combo into one that satisfies the new requirements.

SAMPLE INPUT:

SAMPLE OUTPUT:

The optimal solution in this example is to change the a into b, change the d into e, and then change both e’s into c’s. This will take $1 + 4 + 0 + 0 = 5$ days, and the final combo string will be bbccc.

Problem credits: Eric Wei
<h3>USACO 2019 December Contest, Gold Problem 3. Moortal Cowmbat 题解(翰林国际教育提供，仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>
[/hide]

(Analysis by Eric Wei)

First, note that it is sometimes possible to change a letter to a different one in faster time than what is originally given. To deal with this, we run Floyd-Warshall on the letters to determine the actual shortest amount of time to change each letter to any other letter.

We can now store the fastest time the letter in each index $i$ can be changed to a different letter $j$ , which we represent in a cost matrix, $c s t [i] [j]$ . After this, we can now utilize prefix sums to speed up future computation. We store this in $p s [i] [j]$ , representing the sum of all $c s t [k] [j]$ for $k \leq i$ .

Finally, we can use DP. Let $d p [i] [j]$ represent the smallest amount of time needed so that the first $i$ letters create a “valid combo” and the last letter is $j$ (so the last $K$ letters are all $j$ ). We also create an array, $d p m i n [i]$ , which represents the minimum value of all $d p [i] [j]$ across all possible $j$ . The transition is as follows:

dp[i][j] = min(ps[i][j]-ps[i-K][j]+dpmin[i-K],dp[i-1][j]+cst[i][j]);

There are two possibilities we must consider: either the rightmost streak is exactly $K$ letters long, or it is more than that, corresponding to these two possibilities. Calculating $d p m i n$ is easy from this, and the final answer is simply $d p m i n [N]$ . The runtime is $O (M^{3} + N \cdot M)$ . My code follows:

#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
 
#define MN 100005
#define MA 26
int n, m, k;
string s;
int d[MA][MA];
int cst[MN][MA];
int ps[MN][MA];
int dp[MN][MA];
int mn[MN];
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    freopen("cowmbat.in", "r", stdin);
    freopen("cowmbat.out", "w", stdout);
 
    cin >> n >> m >> k >> s;
    F0R(i, m) F0R(j, m) cin >> d[i][j];
    F0R(c, m) F0R(a, m) F0R(b, m)
        d[a][b] = min(d[a][b], d[a][c]+d[c][b]);
 
    FOR(i, 1, n){
        F0R(j, m){
            cst[i][j] = d[s[i-1]-'a'][j];
            ps[i][j] = ps[i-1][j]+cst[i][j];
            //cout << i << " " << j << " " << cst[i][j] << "\n";
        }
    }
    memset(dp, 0x3f, sizeof dp);
    memset(mn, 0x3f, sizeof mn);
    mn[0] = 0;
 
    FOR(i, 1, n){
        F0R(j, m){
            dp[i][j] = min(dp[i][j], dp[i-1][j]+cst[i][j]);
            if (i >= k) dp[i][j] = min(dp[i][j], ps[i][j]-ps[i-k][j]+mn[i-k]);
            //cout << "dp " << i << " " << j << " " << dp[i][j] << "\n";
            mn[i] = min(mn[i], dp[i][j]);
        }
    }

    cout << mn[n] << "\n";
}

[/hide]