第341场周赛

1. 一最多的行

class Solution {
public:
    vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
        int m =mat.size(); int n = mat[0].size();
        int res = 0;
        int index = 0;
        for(int i=0;i<m;i++){
            int count = 0;
            for(int j=0;j<n;j++){
                if(mat[i][j]==1) count++;
            }
            if(count>res){res = count; index = i;}
        }
        return {index,res};
    }
};

2. 找出可除性得分最大的整数

class Solution {
public:
    int maxDivScore(vector<int>& nums, vector<int>& divisors) {
        sort(nums.begin(),nums.end());
        int res = 0;
        int num = divisors[0];
        for(int i=0;i<divisors.size();i++){
            int score = 0;
            for(int j=0;j<nums.size();j++){
                if(nums[j]%divisors[i]==0) score++;
            }
            if(score>res){res=score; num = divisors[i];}
            else if(score==res&&divisors[i]<num) num = divisors[i] ;
        }
        return num;
    }
};

3. 构造有效字符串的最少插入数

class Solution {
public:
    int addMinimum(string word) {
        if(word.size()==0) return 0;
        else if(word.size()==1) return 2;
        if(word[0]<word[1]){
            if(word.size()==2) return 1;
            else if(word[1]<word[2]) return addMinimum(word.substr(3));
            else return 1+addMinimum(word.substr(2));
        }
        else return 2+addMinimum(word.substr(1));
    }
    
};

4. 最小化旅行的价格总和

分析：选择不相邻节点减半价格并最小化价格
涉及到图的选择的问题，考虑使用回溯法，选择为当前节点减半或者不减半，并递归搜索相邻节点
不过该题首先要知道哪些点走了几次，可以根据路径选择事先用回溯法得到每个点的访问次数
然后根据访问次数与价格生成权重，使用权重做后面的减半回溯搜索，找到最小化解

class Solution {
public:
    vector<vector<int>> graph;//无向邻接表
    vector<int> cnt;//走完指定路径每个点通过的次数
    vector<int> weight;//顶点的代价
    bool confirm;
    int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
        graph.resize(n);
        for (auto& edge : edges) {//初始化
            int from = edge[0];
            int to = edge[1];
            graph[from].push_back(to);
            graph[to].push_back(from);
        }

        cnt.resize(n);
        for (auto& edge : trips) {//用路径初始化经过点的次数
            int from = edge[0];
            int to = edge[1];
            confirm = 0;//当前路径是否找到
            dfs(from, to, -1);//根据起点终点对经过的点计数
        }
        weight.resize(n);
        for (int i = 0; i < n; i++) 
            weight[i] = cnt[i] * price[i];//计算某顶点的代价
        int res = reduce(0, 0, -1);//再次深度优先计算最小路径和
        return res;
    }
    void dfs(int start, int end, int from) {//计算经过各顶点的次数
        if(start==end){cnt[end]++; confirm = 1; return;}
        if (confirm) return;//如果其他路径找到了，就不需要再找了，直接剪枝
        cnt[start]++;//选择当前路径，计数起点

        int n = graph[start].size();
        for (int i = 0; i < n; i++) {
            if (graph[start][i] == from) continue;//不从原路返回
            dfs(graph[start][i], end, start);//选择下一个节点作为起始节点
        }
        if (confirm) return;//当前路径找到了，不需要再撤回
        cnt[start]--;//撤销选择
    }
    long reduce(bool before, int cur, int from) {
        int n = graph[cur].size();
        if (n == 1 && graph[cur][0] == from) {//边界条件，只有一条边，且刚从那边过来
            if (before == 0) return weight[cur] / 2;
            else return weight[cur];
        }
        //权重为0无所谓区不区分,全按不减半处理
        if(weight[cur]==0) {
            int res = 0;
            for (int i = 0; i < n; i++) {//当前节点减半
                if (graph[cur][i] == from) continue;
                res += reduce(0, graph[cur][i], cur);
            }
            return res;
        } 
        //当前节点减半
        int half = INT_MAX;
        if (before == 0) {//前一个节点没有减半
            half = weight[cur] / 2;
            for (int i = 0; i < n; i++) {//当前节点减半
                if (graph[cur][i] == from) continue;
                half += reduce(1, graph[cur][i], cur);
            }
        }
        //当前节点全值
        int total = weight[cur];//当前节点不减半
        for (int i = 0; i < n; i++) {
            if (graph[cur][i] == from) continue;
            total += reduce(0, graph[cur][i], cur);
        }
        return min(half, total);
 } 
};