Weekly Contest 403

日期 2024/06/23
目前可以穩定第一跟第二題，第三題大致上就是 Blind 75 基本題。不過我總是想不出來啊哈哈， Dynamic Programming 好難喔。

• Minimum Average of Smallest and Largest Elements
• Find the Minimum Area to Cover All Ones I
• Maximize Total Cost of Alternating Subarrays
• Find the Minimum Area to Cover All Ones II

第一題

double minimumAverage(vector<int>& nums) {
    const int n = nums.size();
    sort(nums.begin(), nums.end());
    double s = 50;
    for(int i = 0; i < n / 2; i++) {
        double x = nums[i] + nums[n - i - 1];
        x = x / 2;
        s = min(x, s);
    }
    return s;
}

第二題

int minimumArea(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    vector<int> rows(m, 0);
    vector<int> cols(n, 0);
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            rows[i] |= grid[i][j];
            cols[j] |= grid[i][j];
        }
    }

    int l1 = 0;
    for(int i = 0; i < m; i++) {
        if(rows[i]) {
            l1 = i;
            break;
        }
    }

    int l2 = 0;
    for(int i = 0; i < m; i++) {
        if(rows[m - i- 1]) {
            l2 = m - i - 1;
            break;
        }
    }

    int c1 = 0;
    for(int j = 0; j < n; j++) {
        if(cols[j]) {
            c1 = j;
            break;
        }
    }

    int c2 = 0;
    for(int j = 0; j < n; j++) {
        if(cols[n - j - 1]) {
            c2 = n - j - 1;
            break;
        }
    }
    return (l2 - l1 + 1) * (c2 - c1 + 1);
}

第三題

Dynamic Programming 問題。果然我自己缺乏動態轉移規劃的能力，題目類似於 House Robber 問題，參考討論區：

• 討論區 1
• 討論區 2
• notTake 之後可以接 Take 與 notTake
• Take 之後只能接 notTake

using ll = long long;
    vector<vector<ll>> dp;
    long long maximumTotalCost(vector<int>& nums) {
        dp = vector<vector<ll>>(nums.size(), vector<ll>(2, -1));
        return nums[0] + solve(nums, 1, 1);
    }

    ll solve(vector<int> &nums, int start, int f) {
        const int n = nums.size();
        if(start >= n)
            return 0;

        if(dp[start][f] != -1)
            return dp[start][f];

        ll take = -1e15;
        ll notTake = -1e15;
        if(f == 1)
            notTake = (-nums[start]) + solve(nums, start + 1, 0);
        
        take = nums[start] + solve(nums, start + 1, 1);
        dp[start][f] = max(take, notTake);
        return dp[start][f];
    }

第四題