算法提高课汇总

算法思路

本题可以转化成复杂图论问题, 但由于数据量较小, 可以用$dfs$搜索求解.

搜索方式

$dfs$的核心 — 一种快速搜索所有可行方案的搜素方式:

• 可以按组搜索: 依次搜索当前组可以放入哪些数字.

优化

1) 对于每个数字有2个决策:

1. 放入当前组(由于按组依次考虑, 当前组是当前所有组的最后一个组).
2. 新开一组.

若对于某个数字这两个决策都可行, 我们只需要考虑第一个决策, 也就是把能加入当前组的
数字全部加入. 可以证明这种方式不会影响最优解.

假设对于数字p, 其可以加入第$k$组, 也可以为其新开一组$k + 1$.
若新开一组$k + 1$, 算法在此次决策的后续过程中第$k$组不会再加入数字 — 我们是按组依次考虑的.
假设此次决策得到最优解, 由于在判断p可以加入$k$组后, $k$组没有新加入数字, 所以我们可以将
p放入$k$组, 对最优解无影响. 也就是按照能加入当前组就加入的思路, 不会影响最优解数值.

2) 考虑组内数字的集合是一个组合问题, 而不是排列问题.

• 我们可以在考虑每组加入哪些数字时, 人为规定一个顺序 — 一般按照下标递增的顺序, 以防止考虑
  多余的情况.

具体实现

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;

int n, ans = N;
int p[N];
int group[N][N];
bool st[N];

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

bool check(int g[], int x, int length)
{//判断x是否与当前组内所有数字互质
    for ( int i = 0; i < length; i ++ )
        if ( gcd(g[i], x) > 1 )
            return false;
    return true;
}

//gi: 当前组编号; gc: 当前组有多少数字; tc: 总共考虑了多少数字; start: 当前组已经考虑的下标
void dfs(int gi, int gc, int tc, int start)
{
    if ( gi >= ans )    return; //剪枝 不需要继续考虑
    if ( tc == n )
    {//全部考虑完毕
        ans = gi;
        return;
    }

    bool flag = true; //是否要新开一组(当前组已经不能加新数字了)
    for ( int i = start; i < n; i ++ ) //组内按下标升序考虑
    {
        if ( !st[i] && check(group[gi], p[i], gc) )
        {
            st[i] = true;
            group[gi][gc] = p[i];
            dfs(gi, gc + 1, tc + 1, i + 1);
            st[i] = false;

            flag = false;
        }
    }
    if ( flag ) dfs(gi + 1, 0, tc, 0); //新开一组
}

int main()
{
    cin >> n;
    for ( int i = 0; i < n; i ++ )  cin >> p[i];

    dfs(0, 0, 0, 0);
    cout << ans + 1 << endl;

    return 0;
}