Leetcode 周赛题解 218

ACM算法日常

发布于 2020-12-31 10:10:52

3670

发布于 2020-12-31 10:10:52

文章被收录于专栏：ACM算法日常ACM算法日常

https://leetcode-cn.com/contest/weekly-contest-219/

难度顺序：

A\le B\le C\le D

。

5625. 比赛中的配对次数

「提示：」

1 <= n <= 200

「思路：」

按题意模拟即可。

时间复杂度：

O(log(n))

class Solution {
public:
    int numberOfMatches(int n) {
        int ans = 0;
        while(n != 1) {
            if(n & 1) {
                ans += (n - 1) / 2;
                n = n / 2 + 1;
            } else {
                ans += n / 2;
                n /= 2;
            }
        }
        return ans;
    }
};

5626. 十-二进制数的最少数目

「提示：」

1 <= n.length <= 10^5
n 仅由数字组成
n 不含任何前导零并总是表示正整数

「思路：」很明显只要找到数位最大值就可以配出和为

。

时间复杂度：

O(n.length)

class Solution {
public:
    int minPartitions(string n) {
        int num = 0;
        for(int i = 0;i < n.size();i++) {
            num = max(num,n[i] - '0');
        }
        return num;
    }
};

5627. 石子游戏 VII

「提示：」

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

「思路」

很明显这是一个博弈

，爱丽丝要选择使得差值更大的子状态，鲍勃要选择使得差值更小的子状态。

定义pair<int,int> dp[l][r][0/1]代表选择

[l,r]

之间石头，且当前先手的人为(爱丽丝/鲍勃)，得到最优决策下两人的权值。

子状态就是选择左边的石头或者选择右边的石头：对于状态

dp[l][r][cur]

，设

sum

数组为前缀和，

nex=1-cur

，则有

dp[l][r][cur]=(dp[l+1][r].second+sum[r]-sum[l],dp[l+1][r].first)

或者

dp[l][r][cur]=(dp[l][r-1].second+sum[r-1]-sum[l-1],dp[l][r-1].first)

根据先手的人来选择差值最小（最大）的子状态即可。
kickstart Round F 2020 Painters‘ Duel 与这题类似。

时间复杂度：

O(n^2)

class Solution {
public:
    int sum[1005];
    pair<int,int>dp[1005][1005];
    int vis[1005][1005];
    pair<int,int> dfs(int l,int r,int flag) {
        if(l >= r) return {0,0};
        if(vis[l][r]) {
            return dp[l][r];
        }
        pair<int,int>t1 = dfs(l,r - 1,flag ^ 1);
        pair<int,int>t2 = dfs(l + 1,r,flag ^ 1);
        t1 = {t1.second + sum[r - 1] - sum[l - 1],t1.first};
        t2 = {t2.second + sum[r] - sum[l],t2.first};
        if(flag) { //增加差值
            if(t1.first - t1.second > t2.first - t2.second) {
                dp[l][r] = t1;
                vis[l][r] = 1;
                return t1;        
            } else {
                dp[l][r] = t2;
                vis[l][r] = 1;
                return t2;
            }
        } else {
            if(t1.second - t1.first > t2.second - t2.first) {
                dp[l][r] = t2;
                vis[l][r] = 1;
                return t2;
            } else {
                dp[l][r] = t1;
                vis[l][r] = 1;
                return t1;
            }
        }
    }
    int stoneGameVII(vector<int>& stones) {
        for(int i = 0;i < stones.size();i++) {
            int x = stones[i];
            sum[i + 1] = sum[i] + x;
        }
        pair<int,int>ans = dfs(1,stones.size(),1);
        return ans.first - ans.second;
    }
};

5245. 堆叠长方体的最大高度

「提示：」

n == cuboids.length
1 <= n <= 100
1 <= widthi, lengthi, heighti <= 100

「思路」

由于长方体可以旋转，所以我们将每个长方体扩展为6份，代表其旋转后的长宽高。因为下面的长方体长宽高都大于等于上面的，所以我们将长方体按照体积排序。
定义

dp[i]

为将第

个长方体作为最顶上长方体时能得到的最大高度，则有

dp[i]=dp[j]+a[i].z，j>i

，

a[i].z

代表第

个长方体的高度

但是这样转移可能有问题，就是同一个长方体分为了多份，可能用多次，所以我们要特判掉这种情况，转移的时候如果两个长方体是同一个，就跳过。

时间复杂度：

O(n^2*6)

const int maxn = 1005;
struct Node {
    int x,y,z;
    int id;
    
}a[maxn];
int cmp(Node x,Node y) {
    return x.x * x.y * x.z < y.x * y.y * y.z;
}
class Solution {
public:
    int dp[1005],cnt = 0;
    int dfs(int now) {
        if(dp[now] != -1) return dp[now];
        int ans = a[now].z;
        for(int i = now + 1;i <= cnt;i++) {
            if(a[now].id == a[i].id) continue;
            if(a[now].x <= a[i].x && a[now].y <= a[i].y && a[now].z <= a[i].z) {
                ans = max(ans,dfs(i) + a[now].z);
            }
        }
        return dp[now] = ans;
    }
    int maxHeight(vector<vector<int>>& cuboids) {
        memset(dp,-1,sizeof(dp));
        for(int i = 0;i < cuboids.size();i++) {
            a[++cnt] = {cuboids[i][0],cuboids[i][1],cuboids[i][2],i};
            a[++cnt] = {cuboids[i][0],cuboids[i][2],cuboids[i][1],i};
            a[++cnt] = {cuboids[i][1],cuboids[i][0],cuboids[i][2],i};
            a[++cnt] = {cuboids[i][1],cuboids[i][2],cuboids[i][0],i};
            a[++cnt] = {cuboids[i][2],cuboids[i][0],cuboids[i][1],i};
            a[++cnt] = {cuboids[i][2],cuboids[i][1],cuboids[i][0],i};
        }
        sort(a + 1,a + 1 + cnt,cmp);
        int ans = 0;
        for(int i = 1;i <= cnt;i++) {
            ans = max(ans,dfs(i));
        }
        return ans;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-12-13，如有侵权请联系 cloudcommunity@tencent.com 删除

int

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

int

登录后参与评论

0 条评论

热度