POJ3590 The shuffle Problem [置换+dp]

$TheshuffleProblem$The shuffle Problem

$Description$Description

给出正整数 $N$N, $N\&lt;=100$N<=100, 输出长度为 $N$N 的置换的 最长周期, 并请输出满足条件的 字典序最小 的置换 .

$Solution$Solution

$最初想法$最初想法
整个序列的循环节周期长度为所有 子循环节 周期长度 的最小公倍数 .

思维卡点: 每个子循环节的周期长度怎么求呢 ?

$正解部分$正解部分
原来每个子循环节的周期长度是确定的 :

• 作为子循环节不能被划分成其他更小的子循环节
• 经过观察, 每个不可划分的子循环节周期长度都等于其本身长度,

所以得出结论: $子循环节的周期长度等于本身长度$子循环节的周期长度 等于 本身长度,

到此, 问题就转化为: 将数 $N$N划分为若干份, 使 $LCM$LCM 尽量大.

设 $F[i,j]$F[i,j] 表示 将 $i$i 分为 $j$j 份所得到的最大 $LCM$LCM,
则 $F[i,j]=max\left\{lcm\right(F[i-k,j-1],k),F[i,j\left]\right\}$F[i,j]=max{ lcm(F[i−k,j−1],  k), F[i,j] }
转移复杂度 $O\left(N^3\right)$O(N3) .

$如何输出字典序最小的方案?$如何输出字典序最小的方案?

首先最优值 $Ans$Ans 已经被前面的 $Dp$Dp 解决,
这个 $Ans$Ans 为所有区间长度的 $LCM$LCM,
则将其 $分解质因数$分解质因数, 得到 $p_1^{a_1},p_2^{a_2},p_3^{a_3}...p_m^{a_m}$p1a1​​,p2a2​​,p3a3​​...pmam​​,
每个带幂质数都代表着一个区间, 长度分别为 $p_1^{a_1},p_2^{a_2},p_3^{a_3}...p_m^{a_m}$p1a1​​,p2a2​​,p3a3​​...pmam​​,.

可能还会剩余一些 $1$1, 虽说对 $LCM$LCM 没有贡献, 但还是要输出的, 输出 $N-p_1^{a_1}-p_2^{a_2}-p_3^{a_3}...-p_m^{a_m}$N−p1a1​​−p2a2​​−p3a3​​...−pmam​​ 个 $1$1 在前面 $保证字典序最小$保证字典序最小
尽量将小的放到前面, 可以 $保证字典序最小$保证字典序最小, 拿纸画一下就出来了.

$Code$Code

#include<cstdio>
#include<algorithm>
#define reg register

const int maxn = 108;

int T;
int N;
int cnt[maxn];
int F[maxn][maxn];
int Pre[maxn][maxn];
int p[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107};

int Gcd(int a, int b){ return !b?a:Gcd(b, a%b); }
int Lcm(int a, int b){ return a/Gcd(a, b) * b; }

void Work(){
        scanf("%d", &N);
        printf("%d ", F[N][0]);
        int tmp = F[N][0], Ps = 0;
        for(reg int i = 1; i <= 26; i ++){
                cnt[i] = 1;
                while(tmp % p[i] == 0) cnt[i] *= p[i], tmp /= p[i];
                if(cnt[i] == 1) cnt[i] = 0;
                Ps += cnt[i];
        }
        int t = N - Ps;
        for(reg int i = 1; i <= t; i ++) printf("%d ", i);
        t ++;
        std::sort(cnt+1, cnt+26+1);
        for(reg int i = 1; i <= 26; i ++){
                if(!cnt[i]) continue ;
                int tmp = t;
                for(reg int j = 1; j < cnt[i]; j ++) printf("%d ", t+j);
                printf("%d ", tmp);
                t += cnt[i];
        }
        printf("\n");
}

int main(){ 
        for(reg int i = 1; i <= 105; i ++){
                F[i][1] = i;
                for(reg int j = 2; j <= i; j ++)
                        for(reg int k = 1; k <= i; k ++)
                                F[i][j] = std::max(Lcm(F[i-k][j-1], k), F[i][j]);
        }
        for(reg int i = 1; i <= 105; i ++) 
                for(reg int j = 1; j <= i; j ++) F[i][0] = std::max(F[i][0], F[i][j]);
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}