P9836 种树

Kdlyh · 2023-11-12 20:01:42 · 题解

动态规划思路

可行性

抛开取模问题和空间限制，该题存在最优子结构性和无后效性，而这两个问题都可以另外处理。

状态定义

## 状态转移 ### 先忽略取模问题 #### 推导状态转移方程 - 不选择对当前第$\space i\space$个树木施肥。显而易见，$F_{i,j}\space$应该从前$\space i - 1\space$棵树，剩余$\space j\space$单位化肥的状态再乘以当前的高度因子数转移而来。 $$F_{i,j}=F_{i-1,j}\times \operatorname{getInShu}(p_i)$$ - 选择对当前第$\space i\space$个树木施肥。 $\space F_{i,j}\space$应该从前$\space i-1\space$棵树，剩余$\space j\times k\space$单位化肥转移过来。这里的 $j\times k$ 必须满足两个条件： - $j\times k \leq w

显然必须小于总化肥量。
- 从题干中（**要求 $\space k\space$ 必须为当前化肥量的正因数**）推出，所有状态的**当前化肥量**显然只能是总化肥量 $ \space w \space$ 的正因数。

由此可以推导出，j\times k\space就是\space w\space的正因子。

预处理出来\space w\space的所有正因子存入\space fertilizer\space 数组中，并找出大于当前剩余 j 单位化肥且当前剩余\space j\space单位化肥是其正因子的\space fertilizer_i，即为待转移状态的剩余单位化肥量，此处设为\space j'。

F_{i,j}=\max(F_{i-1,j},F_{i-1,j'}+\operatorname{getInShu}(p[i]\times(j'\div j))

代码实现

首先初始化初状态

F[0][w] = 1;

即剩下\space w\space化肥量（还没用过化肥时）的初状态。

状态转移实现

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= nfy; j++)
    {
        F[i][fertilizer[j]] = F[i - 1][fertilizer[j]] * getInShu(p[i]);
        for (int k = j + 1; k <= nfy; k++)
        {
            if (fertilizer[k] % fertilizer[j] == 0)//判断当前数是否是w正因子的正因子
            {
                ll temp = fertilizer[k] / fertilizer[j];//temp剩余的化肥量除的数 
                F[i][fertilizer[j]] = max(F[i - 1][fertilizer[k]] * getInShu(p[i] * temp), F[i][fertilizer[j]]);
            }
        }
    }
}

到此，我们算是在无视取模和空间限制的情况下完成了状态转移。

快速求因子数

问题来由

用动态规划实现复杂度接近于\space \operatorname{O}(n^2)，此时再用平常的\space \operatorname{O}(\sqrt n)\space算法来求因子数会导致超时。

处理方法

依靠两个结论

一个正整数一定能分解为若干质数\space n\space次方的乘积。
一个数的因子数等于该数分解为若干质数\space n\space次方的乘积后每个质数的次方数加一的乘积。

举个例子

120=2^3\times3\times5

那么因子数则是\space (3+1)\times(1+1)\times(1+1)=16。

代码实现

ll getInShu(ll n)
{
    ll ans = 1;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)//质因数分解
        {
            ll cnt = 0;//即这个因数的次方
            while(n % i == 0)
            {
                ++cnt;
                n /= i;
            }
            ans = (ans mod) * ((cnt + 1) mod);
            ans = ans mod;
        }
    }
    if (n != 1)//说明剩下最后一个质因数
    {
        ans *= 2;
    }
    return ans mod;
}

处理取模问题

问题来由

最优性问题每次都要判断大小，而取模判断大小很可能出现各种问题。

比如假设对\space 1000\space取模，比较\space 99\space和\space 1001\space的大小，显然两数取模\space 99>1，出现了问题。

而动态规划时每次判断最优解就会被这个问题影响正确性。

处理方法

仅针对本题，取模的对象是通过乘法进行状态转移的，那么问题就转移到了如何正确的在状态转移时判断两个状态的大小。

除了习惯性的直接比较两个状态的大小外，可以利用乘法的性质，即两数相乘与两数对数相加正相关。

如此，我们维护一个数组 DP，DP 和 F 数组同步操作，只是所有的相乘改为取对数相加。显然对数的数量级不会越界，不需要取模，也保证了正确性。

代码实现非常容易，即所有的相乘操作都换成对数相加。

初始化加入：

dp[0][w] = log(1);

不选择对当前第\space i\space个树木施肥。

dp[i][fertilizer[j]] = dp[i - 1][fertilizer[j]] + log(getInShu(p[i]));

选择对当前第\space i\space个树木施肥。

dp[i][fertilizer[j]] = dp[i - 1][fertilizer[k]] + log(getInShu(p[i] * temp));

优化空间

问题来由

本题的\space N\space和\space W\space都到了\space 10^4\space 的大小，这意味着如果使用二维数组，需要开\space 10^8\space个 long 和 double。

这导致了 MLE。

处理方法

`MAP` 思路

从状态转移方程的推导不难看出，因为剩余化肥数只能从\space w\space的所有正因子中选（一个数的正因子数肯定小于这个数本身，数越大越明显），而第二维却开了\space w\space个空间，即用来表示剩余化肥数的维度是存在大量浪费的。

有什么办法能解决呢，蒟蒻我觉得最好实现的就是用 map 来维护两个动态规划数组。

map 本质上也是个容器，但是它只有用到了才会开辟空间，即放入这个元素到 map 容器内。

这真正做到了没用到的就不开辟空间。

实现

即维护一个 map<pair<int, int>, int or double>。

pair 用来替代动规数组的两维，而 int 或 double 用来存动规数组的值。

代码非常简单，首先开辟两个动规数组。

map<pair<int, int>, long long> F; 
map<pair<int, int>, double> dp;

之后把原来代码所有的下标改为 pair 即可。

F[i][j] = k -> F[{i, j}] = k;

滚动数组思路

经 @User439000 提醒，我发现这题也完全可以用滚动数组优化。

由于对 f_{i,j} 有影响的只有 f_{i - 1,j}，可以去掉第一维，直接用第二维来表示状态转移。

F_{j}=\max(F_{j}\times \operatorname{getInShu}(p_i),F_{j'}+\operatorname{getInShu}(p[i]\times(j'\div j))

实现

首先开两个一维数组来代替 F 和 dp。

由于滚动数组的更新仍需要从上一个状态开始，而本动态规划算法的状态更新是每轮从剩余肥料大到小更新的。

因此第二层枚举当前肥料剩余量的循环应从小到大，这样可以保证每次更新时使用的是上一次更新的状态。

for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= nfy - 1; j++)
        {
            dp[fy[j]] = dp[fy[j]] + log(getInShu(p[i]));
            F[fy[j]] = (F[fy[j]] mod) * (getInShu(p[i]) mod);
            F[fy[j]] = F[fy[j]] mod;
            for (int k = nfy; k >= j + 1; k--)
            {
                if (fy[k] % fy[j] == 0)
                {
                    ll temp = fy[k] / fy[j];
                    if (dp[fy[j]] < dp[fy[k]] + log(getInShu(p[i] * temp)))
                    {
                        dp[fy[j]] = dp[fy[k]] + log(getInShu(p[i] * temp));
                        F[fy[j]] = ((F[fy[k]]mod) * (getInShu(p[i] * temp)mod))mod;
                    }
                }
            }
        }
    }

代码实现

`map` 优化内存实现

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>

#define mod %998244353 
#define ll long long

const int N = 1e4 + 10;

using namespace std;

int n, w;
int p[N];
int fertilizer[N], nfy;
ll ans = -1;
map<pair<int, int>, long long> F; 
map<pair<int, int>, double> dp;

ll getInShu(ll n)
{
    ll ans = 1;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ll cnt = 0;
            while(n % i == 0)
            {
                ++cnt;
                n /= i;
            }
            ans = (ans mod) * ((cnt + 1) mod);
            ans = ans mod;
        }
    }
    if (n != 1)
    {
        ans *= 2;
    }
    return ans mod;
}

void setFertilizer()
{
    for (int i = 1; i <= w; i++)
    {
        if (w % i == 0)
        {
            fertilizer[++nfy] = i;
        }
    }
}

void solveIfWEqualOne()
{
    ll ans = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
        ans = ans * getInShu(p[i])mod;
        ans = ans mod;
    }
    cout << ans mod;
    return;
}

int main()
{
    cin >> n >> w;
    if (w == 1)//即无视了化肥问题，显然直接特判比动规快多了
    {
        solveIfWEqualOne();
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }
    setFertilizer();
    F[{0,w}] = 1;
    dp[{0,w}] = log(1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = nfy - 1; j >= 1; j--)
        {
            dp[{i,fertilizer[j]}] = dp[{i - 1,fertilizer[j]}] + log(getInShu(p[i]));
            F[{i,fertilizer[j]}] = (F[{i - 1,fertilizer[j]}] mod) * (getInShu(p[i]) mod);
            F[{i,fertilizer[j]}] = F[{i,fertilizer[j]}] mod;
            for (int k = nfy; k >= j + 1; k--)
            {
                if (fertilizer[k] % fertilizer[j] == 0)
                {
                    ll temp = fertilizer[k] / fertilizer[j];
                    if (dp[{i,fertilizer[j]}] < dp[{i - 1,fertilizer[k]}] + log(getInShu(p[i] * temp)))
                    {
                        dp[{i,fertilizer[j]}] = dp[{i - 1,fertilizer[k]}] + log(getInShu(p[i] * temp));
                        F[{i,fertilizer[j]}] = ((F[{i - 1,fertilizer[k]}]mod) * (getInShu(p[i] * temp)mod))mod;
                    }
                }
            }
        }
    }
    cout << F[{n, 1}]mod;   
    return 0;
}

滚动数组优化内存实现

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

#define mod %998244353
#define ll long long

const int N = 1e4 + 10;

using namespace std;

int n, w;
int p[N];
int Fertilizer[N], nfy;
ll F[N];
float dp[N];

ll getInShu(ll n)
{
    ll ans = 1;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ll cnt = 0;
            while (n % i == 0)
            {
                ++cnt;
                n /= i;
            }
            ans = (ans mod) * ((cnt + 1) mod);
            ans = ans mod;
        }
    }
    if (n != 1)
    {
        ans *= 2;
    }
    return ans mod;
}

void setFertilizer()
{
    for (int i = 1; i <= w; i++)
    {
        if (w % i == 0)
        {
            Fertilizer[++nfy] = i;
        }
    }
}

void solveIfWEqualOne()
{
    ll ans = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
        ans = ans * getInShu(p[i])mod;
        ans = ans mod;
    }
    cout << ans mod;
    return;
}

int main()
{
    cin >> n >> w;
    if (w == 1)
    {
        solveIfWEqualOne();
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }
    setFertilizer();
    F[w] = 1;
    dp[w] = log(1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= nfy - 1; j++)
        {
            dp[Fertilizer[j]] = dp[Fertilizer[j]] + log(getInShu(p[i]));
            F[Fertilizer[j]] = (F[Fertilizer[j]] mod) * (getInShu(p[i]) mod);
            F[Fertilizer[j]] = F[Fertilizer[j]] mod;
            for (int k = nfy; k >= j + 1; k--)
            {
                if (Fertilizer[k] % Fertilizer[j] == 0)
                {
                    ll temp = Fertilizer[k] / Fertilizer[j];
                    if (dp[Fertilizer[j]] < dp[Fertilizer[k]] + log(getInShu(p[i] * temp)))
                    {
                        dp[Fertilizer[j]] = dp[Fertilizer[k]] + log(getInShu(p[i] * temp));
                        F[Fertilizer[j]] = ((F[Fertilizer[k]]mod) * (getInShu(p[i] * temp)mod))mod;
                    }
                }
            }
        }
    }
    cout << F[1]mod;
    return 0;
}

结语

昨天模拟赛想了三个小时没想出来处理取模问题心态爆炸，觉得自己白想了，自己方法不可行，气的晚上睡不着。

到今天终于把这个做法完善通过，很喜悦。

很多时候路都是走出来的。

十一月十二号二十点整于旗山实验室。

P9836 种树

动态规划思路

可行性

状态定义

代码实现

首先初始化初状态

状态转移实现

快速求因子数

问题来由

处理方法

依靠两个结论

举个例子

代码实现

处理取模问题

问题来由

处理方法

优化空间

问题来由

处理方法

MAP 思路

实现

滚动数组思路

实现

代码实现

map 优化内存实现

滚动数组优化内存实现

结语

`MAP` 思路

`map` 优化内存实现