ARST打卡第204周[204/521]

Linmin.Shan included in ARST

2023-04-02 624 words 2 minutes

Contents

Algorithm

lc1039_多边形三角剖分的最低得分

个人思路: 感觉是让小值的点尽量连接成边，每个点都可以和非相邻的点连边，也就是 n * (n-2) / 2 种连线的不交差并成三角形的组合

因为 n 取值范围是[3, 50]，所以可以尝试状态压缩，然后遍历，检验合法性，然后获取维护最小值

状态压缩: 用 0-50 表示第一个点和其他的点是否连接边，然后用 51-100 表示第二个点是否和其他的点连边

合法性检查:

连边之后，连边一侧的点不能连接到另一侧
三角形检查 (通过每个点都遍历发散3次，第三次的点集合必须有自身)

感觉虽然可以实现解决问题，但是这个思路过于复杂，看看题解有没有什么好的思路

结果题解直接动态规划快速解决了问题，对问题的抽象比我的好一点，学习之

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        unordered_map<int, int> memo;
        int n = values.size();
        function<int(int, int)> dp = [&](int i, int j) -> int {
             if (i + 2 > j) {
                return 0;
            }
            if (i + 2 == j) {
                return values[i] * values[i + 1] * values[j];
            }
            int key = i * n + j;
            if (!memo.count(key)) {
                int minScore = INT_MAX;
                for (int k = i + 1; k < j; k++) {
                    minScore = min(minScore, values[i] * values[k] * values[j] + dp(i, k) + dp(k, j));
                }
                memo[key] = minScore;
            }
            return memo[key];
        };
        return dp(0, n - 1);
    }
};

Review

度过困难时期的一些方法

多和朋友交流情绪
感觉不好的时候，去帮助那些和我们有着相同境遇的人，和那些被我们领导的人

Tips

Cloudflare WARP一键安装脚本使用教程

braft中raft_service.h 文件报错: 命名空间 "butil" 没有成员 "EndPoint"的思考

1

#include <butil/endpoint.h> // https://github.com/baidu/braft/issues/387

发现许多项目编译没问题，但是读代码的时候却有些内容找不到，感觉应该是编译提供了很多工具库的加入一起编译链接，所以提高了鲁棒性

Contents

ARST打卡第204周[204/521]

Algorithm

Review

Tips

Share