本文主要是介绍POJ 3590 The shuffle Problem 置换+DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：对每一个置换T，都存在一个T^k = e。现在让你求一个n元置换，使得它的阶最大，即当T^k = e时，k最大。若同时存在多个这样的T，那么输出其中排序最小的。
题解：由于每一个置换都可以分解成若干个轮换，那么这些轮换的阶的最小公倍数就是该置换的阶。
所以题目可以变成这样：给你一个整数n，求n1+n2+n3```+ni = n。 并且n1,n2,```ni的最小公倍数最大。
1.求最小公倍数并不难，动态规划解决。
2.那么求得最小公倍数之后怎么保证置换排序最小呢？
我们不妨令某个最小公倍数为lcmMax， 那么将lcmMax因式分解之后得到 lcmMax = p1^k1*p2^k2*``pi^ki
并且p1^k1+p2^k2+···+pi^ki <= n。这个是显然的，因为 lcmMax = p1^k1*p2^k2*``pi^ki <= n1*n2*n3```*ni
而n1+n2+n3```+ni = n，所以p1^k1+p2^k2+···+pi^ki <= n。
3.用次用pi^ki个元素构成一个轮换，那么就能保证该置换T的阶最大。
那么你可能会问，剩下的元素怎么办呢？其实全部让它们为一阶轮换就OK了，因为一阶轮换并不影响最后T的阶。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;#define N 110
#define lint __int64
lint dp[N][N], maxLcm[N];
lint factor[N], fnum;
int p[25] ={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};inline lint gcd ( lint a, lint b )
{lint c;while ( b != 0 ){c = a % b;a = b;b = c;}return a;
}void split ( int n )
{int i, j, k, lcm;memset(dp,0,sizeof(dp));for ( i = 1; i <= n; i++ )dp[i][1] = i;for ( i = 2; i <= n; i++ )for ( j = 2; j <= i; j++ )for ( k = 1; k < i && i-k >= j-1; k++ ){lcm = dp[i-k][j-1] * k / gcd(dp[i-k][j-1], k);if ( lcm > dp[i][j] ) dp[i][j] = lcm;}for ( i = 1; i <= n; i++ ){maxLcm[i] = 0;for ( j = 1; j <= n; j++ )if ( dp[i][j] >= maxLcm[i] )maxLcm[i] = dp[i][j];}
}void split ( lint num )
{fnum = 0;for ( int i = 0; i < 25; i++ ){if ( num % p[i] ) continue;factor[fnum] = 1;while ( num % p[i] == 0 ){factor[fnum] *= p[i];num /= p[i];}fnum++;}
}int main()
{int t, n;split(100);scanf("%d",&t);while ( t-- ){scanf("%d",&n);split ( maxLcm[n] );sort(factor,factor+fnum);int i, j, k, tmp = 0;for ( i = 0; i < fnum; i++ )tmp += factor[i];printf("%I64d",maxLcm[n]);for ( i = 1; i <= n - tmp; i++ )printf(" %d",i);k = n - tmp;for ( i = 0; i < fnum; i++ ){for ( j = 2; j <= factor[i]; j++ )printf(" %d",k+j);printf(" %d",k+1);k += factor[i];}printf("\n");}return 0;
}
这篇关于POJ 3590 The shuffle Problem 置换+DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
