POJ3590 The shuffle Problem——置换群+DP/递推预处理

显然，这是一个置换群问题，答案m就是将n这个数拆成k个(1=<k<=n),k个数能够得出的最小公倍数。

简略证明：

序列会被分为若干个群，每个群需要交换这个群的size次才能够回复原位，因此，问题转化成求将n这个数拆成k个(1=<k<=n),k个数能够得出的最小公倍数，以及满足题目要求的字典序最小的序列。

DP预处理：

dp[i][j]表示将i这个数字划分成j个，这j个数能够组成的最小公倍数。那么方程就是dp[i][j]=max{lcm(dp[k][j-1],i-k)}  (j-1<=k<=i-1)

注意，要令字典序最小，必须使划分的集合数尽量多，并按照集合大小从小到大排序，加以匹配即可。

参考代码：

program poj3590;//By_Thispoet
const maxn=100;
var i,j,k,m,n,p,q,test    :longint;
    dp,src                :array[0..maxn,0..maxn]of longint;
    ans                   :array[0..maxn]of longint;
function gcd(i,j:longint):longint;
begin
  if j=0 then exit(i);exit(gcd(j,i mod j));
end;

function lcm(i,j:longint):longint;
var x:longint;
begin
  x:=gcd(i,j);exit(i*j div x);
end;

procedure getans(i,code:longint);
var p,j:longint;
begin
  if code=1 then begin
    inc(ans[0]);ans[ans[0]]:=i;exit;
  end;p:=src[i][code];getans(p,code-1);inc(ans[0]);ans[ans[0]]:=i-p;
end;

procedure swap(var i,j:longint);
begin
  if i<>j then begin i:=i xor j;j:=i xor j;i:=i xor j;end;
end;

procedure qsort(l,r:longint);var i,j,k:longint;
begin
  i:=l;j:=r;k:=ans[(i+j)>>1];repeat
    while ans[i]<k do inc(i);while ans[j]>k do dec(j);
    if i<=j then begin swap(ans[i],ans[j]);inc(i);dec(j); end;
  until i>j;if l<j then qsort(l,j);if i<r then qsort(i,r);
end;

procedure printf(i,code:longint);var j:longint;
begin
  for j:=i+1 to i+ans[code]-1 do write(j,' ');
  if i=n-ans[code]+1 then begin write(i);exit;end;write(i,' ');printf(i+ans[code],code+1);
end;

begin
  readln(test);filldword(dp,sizeof(dp)shr 2,0);
  for i:=1 to 100 do begin dp[i][1]:=i;dp[i][0]:=1;end;
  for i:=1 to 100 do for j:=2 to i do begin
    for k:=i-1 downto j-1 do begin
      p:=lcm(dp[k][j-1],i-k);if p>dp[i][j] then begin
        dp[i][j]:=p;src[i][j]:=k;
      end;
      if dp[i][j]>=dp[i][dp[i][0]] then dp[i][0]:=j;
    end;
  end;
  while test>0 do begin
    readln(n);ans[0]:=0;
    write(dp[n][dp[n][0]],' ');getans(n,dp[n][0]);
    qsort(1,ans[0]);printf(1,1);writeln;
    dec(test);
  end;
end.