Friedforks's blog

CF: Mortal Combat Tower

简单题。。。。。但是题解1调试了我好久，主要是有老6影藏bug

题解1：DP

简单粗暴记忆化搜索所有情况：

状态：dp[i][j]意思是在走到位置j上切到了玩家i\in[0,1]。0=我队友，1=我的时候最少用了多少个skip point。那么答案就是min(dp[0][n],dp[1][n])，在最后看看是落在谁那边用的skip point最少。

初始状态：dp[1][0]=0 代表一开始在0的位置上如果切到了我（虽然不可能因为队友先开始），那么就用了0个skip point。

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int test_case_num;
    cin >> test_case_num;

    for (int t = 0; t < test_case_num; t++) {
        int n;
        cin >> n;

        vector<int> bosses(n);
        for (int j = 0; j < n; j++) {
            cin >> bosses[j];
        }

        /*
         * dp[i][j] = the min amount of skip points
         * on turn i (your turn is 0), on the jth boss.
         * (1e9 to prevent overflow)
         */
        vector<vector<int>> dp(2, vector<int>(n + 1, 1e9));

        /*
         * base case:
         * your friend uses zero skip points before fighting any bosses.
         */
        dp[1][0] = 0;

        for (int j = 0; j < n; j++) {
            // the opposite player switches on the previous move.
            dp[0][j + 1] = min(dp[0][j + 1], dp[1][j] + bosses[j]);
            dp[1][j + 1] = min(dp[1][j + 1], dp[0][j]);

            // the opposite player switches from the previous two moves.
            if (j + 2 <= n) {
                dp[0][j + 2] =
                    min(dp[0][j + 2], dp[1][j] + bosses[j] + bosses[j + 1]);
                dp[1][j + 2] = min(dp[1][j + 2], dp[0][j]);
            }
        }
        cout << min(dp[0][n], dp[1][n]) << endl;
    }
}

恶心的点在于，因为要求min，那么数组初始化得是无穷大吧？但是bug在于我如果设为INT_MAX，在dp的过程中会在此之上再增加，以至于他整数型溢出变成INT_MIN，然后因为一直取min，所以被carry到了结尾输出一个INT_MIN。我debug了半天没想到是这个老六……

给他设小一点，设为1e9就OK了，这样不会整数型溢出。

题解2：贪心

一开始必定是队友，所以第一个位置该用sp就用了，关键是后面怎么选择切人。

1 1 1 1 1 1

考虑一串连续的1，那么最优的情况应该是两个1我来，切（也必须切）队友用一个sp，然后再让我来打两个……

可以观察出结论（有点难，我也是看题解的）：在k个连续的1的子序列最少需要\lfloor \frac{k}{3} \rfloor 个sp。所以，只需要数连续1序列长度，计算sp使用，结束。

代码（非原创Educational Codeforces Round 95 Editorial - Codeforces）：

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &it : a) cin >> it;
        int ans = 0;
        ans += a[0] == 1;
        for (int i = 1; i < n; ++i) {
            if (a[i] == 0) {
                continue;
            }
            int j = i;
            while (j < n && a[j] == 1) {
                ++j;
            }
            ans += (j - i) / 3;
            i = j - 1;
        }
        cout << ans << endl;
    }
  
    return 0;
}

CF: Mortal Combat Tower

CF: Mortal Combat Tower

题解1：DP

题解2：贪心

评论