Tanya and Colored Candies

Created by LXC on Wed Jun 28 08:59:41 2023

https://codeforces.com/problemset/problem/1057/C

ranting: 2000

tag: *special, dp

problem

有n个糖果箱子排成一行，每个箱子有红绿蓝三种颜色。每个箱子内有$r_i$个糖果。

现在你的位置是s，每次移动到相邻的位置需要时间一秒。你可以瞬间收集箱子内的糖果。
但是有个前提是收集时必须与上一次收集的箱子颜色不同且糖果数更多。

求最小收集时间，使得收集至少k个糖果。

solution

定义$dp_{i,j}$为在i位置时恰好收集了j个糖果。

显然有$dp_{i,r_i} = |s-i|$

$dp_{i,j+r_c} = \min \limits_{r_i < r_c \wedge color_i \ne color_c} dp_{i,j} + |c-i|$

需要至少收集k个糖果，每个糖果箱子的糖果数不超过50，所以答案为$\sum \limits_{i=1}^{n} \sum \limits_{j=k}^{k+50} dp_{i,j}$

此外，另一种做法是定义$dp_{i,j}$为在i位置时至少收集了j个糖果。

状态转移
$dp_{i,j} = \min \limits_{r_i > r_c \wedge color_i \ne color_c} dp_{c,j-r_c} + |c-i|$

递归边界
当递归到$dp_{i,j}, r_i>=j$时，这时收集了$r_i$就会让整体收集个数大于等于k，只需要从s移动到i即可，即$dp_{i,j}=abs(i-s)$。

我们还可以将递归写为递推的形式。

code

定义$dp_{i,j}$为在i位置时恰好收集了j个糖果。

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
#define INF 0x3f3f3f3f
using namespace std;

void sol() {
    int n, s, k;
    cin >> n >> s >> k;
    s--;
    vector<int> r(n);
    for (auto& i : r)
        cin >> i;
    string c;
    cin >> c;
    vector<vector<int>> f(n, vector<int>(k + 51, INF));
    for (int i = 0; i < n; i++) {
        f[i][r[i]] = abs(i - s);
    }
    for (int j = 0; j <= k; j++) {
        for (int i = 0; i < n; i++) {
            for (int z = 0; z < n; z++) {
                if (c[i] == c[z] || r[i] >= r[z])
                    continue;
                f[z][j + r[z]] = min(f[z][j + r[z]], f[i][j] + abs(i - z));
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= 50; j++) {
            ans = min(ans, f[i][j + k]);
        }
    }
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j <= k; j++) {
    //         cout << i << " " << j << " " << f[i][j] << "\n";
    //     }
    // }
    if (ans == INF)
        cout << "-1\n";
    else
        cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

$dp_{i,j}$为在i位置时至少收集了j个糖果。记忆化搜索

void sol() {
    int n, s, k;
    cin >> n >> s >> k;
    s--;
    vector<int> r(n);
    for (auto& i : r)
        cin >> i;
    string c;
    cin >> c;
    vector<vector<int>> f(n, vector<int>(k + 1, INF * 2));
    // 在x位置还有y个要收集,所需的最小时间
    function<int(int, int)> dfs = [&](int x, int y) {
        if (r[x] >= y) {
            // return f[x][y] = min(abs(x - s), f[x][y]);
            return f[x][y] = abs(x - s);
        }
        if (f[x][y] != INF * 2)
            return f[x][y];
        f[x][y] = INF;
        for (int i = 0; i < n; i++) {
            if (c[x] != c[i] && r[i] < r[x])
                f[x][y] = min(f[x][y], dfs(i, y - r[x]) + abs(i - x));
        }
        return f[x][y];
    };
    int ans = INF;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dfs(i, k));
    }
    if (ans == INF) {
        cout << "-1\n";
    } else {
        cout << ans << "\n";
    }
}

$dp_{i,j}$为在i位置时至少收集了j个糖果。递推

void sol() {
    int n, s, k;
    cin >> n >> s >> k;
    s--;
    vector<int> r(n);
    for (auto& i : r)
        cin >> i;
    string c;
    cin >> c;
    vector<vector<int>> f(n, vector<int>(k + 1, INF));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= r[i]; j++)
            f[i][j] = abs(i - s);
    }
    // 在x位置还有y个要收集,所需的最小时间
    for (int y = 0; y <= k; y++) {
        for (int x = 0; x < n; x++) {
            for (int i = 0; i < n; i++) {
                if (c[x] != c[i] && r[i] < r[x]) {
                    f[x][y] = min(f[x][y], f[i][max(0, y - r[x])] + abs(i - x));
                }
            }
        }
    }
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j <= k; j++) {
    //         cout << i << " " << j << " " << f[i][j] << "\n";
    //     }
    // }
    int ans = INF;
    for (int i = 0; i < n; i++) {
        ans = min(ans, f[i][k]);
    }
    if (ans == INF) {
        cout << "-1\n";
    } else {
        cout << ans << "\n";
    }
}