LeetCode第242场周赛总结

前往竞赛

哪种连续子字符串更长

要是非要分类的话就是DP。

准时到达的列车最小时速

二分，发现倍增二分真好用，有一个函数，将顶函数变成底函数：

⌈ x ⌉ = ⌊ x − 1 ⌋ + 1 \lceil x \rceil = \lfloor x - 1 \rfloor + 1 ⌈x⌉=⌊x−1⌋+1

跳跃游戏 VII

一开始的思想是DP，但是普通的DP会超时，因此使用滑动窗口优化的DP即可。

石子游戏 VIII

我们定义 d p [ i ] dp[i] dp[i]为Alice第一次取到 i i i的最大差值，考虑博弈的对等性，Alice取完之后，Bob开始取，但是前缀和是不变的，因此：

d p [ i ] = ∑ j = 1 i s t o n e s [ i ] − max ⁡ j = i + 1 n d p [ j ] dp[i]=\sum_{j=1}^istones[i]-\max_{j=i+1}^ndp[j] dp[i]=j=1∑i​stones[i]−j=i+1maxn​dp[j]

using ll = long long;

class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        int n = stones.size();
        vector<ll> s(n + 1);
        for (int i = 1; i <= n; ++i)
            s[i] = s[i - 1] + stones[i - 1];
        vector<ll> dp(n + 1);
        ll ans = dp[n] = s[n];
        for (int i = n - 1; i > 1; --i) {
            dp[i] = s[i] - ans;
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
           

这么简单的博弈论都没做出来，ε=(´ο｀*)))唉。