LeetCode Hard

除了搞CTF的，大概只有很少人知道leetcode是一种编码吧 - -。
只做hard
提高一下Python编程能力（我是sb才会用Python做算法题，太艹了）
还有让我秀逗的脑袋思考一下 - -。
——20200509

---

LCP 14. 切分数组

Description

https://leetcode-cn.com/problems/qie-fen-shu-zu/
切分一个数组，切分条件是两端的数不互质，问最少切分组数 $N\leqslant 10^5, nums[i]\leqslant 10^6$

Solution

标准$O(n\log n)$复杂度的数据范围…从数据范围猜复杂度233
首先$O(n^2\log n)$的最暴力的做法很直观吧..
反正是肯定要分解质因数，最初我的想法是分解完了，建图- -，有相同因数的索引两两连边cost为0，相邻的连边cost为1，从1到n跑最短路就得到了，复杂度是$O(n\log n+n^2+n^2)$…
然后dp优化就是，对于每个质数维护一个堆，表示以这个质数开头的最小cost，复杂度就是$O(n\log^2 n)$
嗯，我们不用堆，就是$O(n\log n)$了…单调下降的..
还是说一下具体的方法吧，就是线性筛+DP，线性筛求出每个数的最小质数，听说有人被卡常了??? 这不是$O(10^6)$的吗…
维护两个数组$f[i]$表示以$i$结尾的最小cost，$g[i]$表示以质因数$i$开头的最小cost
对于每个位置$i$，首先分解$nums[i]$，然后维护$g[minp]=min\{g[minp], f[i-1]+1\}$，也就是以当前数字开头的更新；$f[i]=min\{f[i],g[minp]\}$，结尾自然和开头对应，不需要加cost。最后直接返回$f[n]$就ok

ps. 内存击败了100%的用户可还行…
——20200510

Code

const int N = 1e6+50;
const int M = 8e4;
class Solution {
private:
    bool b[N];
    int p[N], cntp;
    int minp[N], minc[N];
    int f[N], g[M];
    int n;

    void init() {
        for(int i=2; i<N; i++) {
            if(!b[i]) p[++cntp]=i, minp[i]=cntp;
            for(int j=1; j<=cntp && p[j]*i<N; j++) {
                b[i*p[j]] = 1; minp[i*p[j]] = j;
                if(i%p[j]==0) break;
            }
        }
    }
public:
    
    int splitArray(vector<int>& nums) {
        // for(int i=0; i<nums.size(); i++) cout << nums[i] << " ";cout << endl;
        n = nums.size();
        init();
        for(int i=1; i<M; i++) g[i]=n;
        for(int i=1; i<=n; i++) {
            int x = nums[i-1]; f[i]=n;
            // cout << x << endl;
            while(x>1) {
                int xminp = minp[x];
                g[xminp]=min(g[xminp], f[i-1]);
                f[i]=min(f[i], g[xminp]+1);
                x/=p[xminp];
            }
        }
        return f[n];
    }
};