LCP 14. 切分数组

LCP 14. 切分数组

const int N = 1e6 + 10;
const int INF = 1e8;
bool st[N];
int prime[N];

class Solution {
 public:
  vector<int> minprimefactor;
  void pre_process() {
    minprimefactor.resize(N, 1);
    memset(st, 0, sizeof st);

    int cnt = 0, x = 1e6;  //线性筛
    for (int i = 2; i <= x; i++) {
      if (!st[i]) {
        prime[cnt++] = i;
        minprimefactor[i] = i;
      }
      for (int j = 0; prime[j] <= x / i; j++) {
        st[prime[j] * i] = true;
        minprimefactor[prime[j] * i] = prime[j];
        if (i % prime[j] == 0) break;
      }
    }
  }

  int splitArray(vector<int>& nums) {
    pre_process();

    int n = nums.size();
    map<int, int> f;
    int x = nums[0];
    while (x != 1) {
      f[minprimefactor[x]] = 1;
      x /= minprimefactor[x];
    }
    int premin = 1;  //上一次最好的结果，就是只分成1个子数组
                     //因为nums[0]就一个数字  也是一个值的初始化
    for (int i = 1; i < n; i++) {
      x = nums[i];
      int curmin = INF;
      while (x != 1) {
        if (f.count(minprimefactor[x]) == 0)
          f[minprimefactor[x]] = premin + 1;
        else
          f[minprimefactor[x]] = min(f[minprimefactor[x]], premin + 1);
          // 如果有序列：2, 5, 3, 2, 3
          // f[minprime[3]] = 3, premin + 1 = 2;
          // 肯定要选择后者
          // 所以新加入一个质因子的时候，有两个选择：
          // 1. 和最前面的相同质因子的数合并到一个区间，不单独开辟新区间
          // 2. 单独算一个区间
        curmin = min(curmin, f[minprimefactor[x]]);
        x /= minprimefactor[x];  //质因数分解
      }
      premin = curmin;
    }
    return premin;
  }
};