POJ3590 The shuffle Problem - 그룹 교환 + DP/점차적 처리
2368 단어 shuffle
서열은 몇 개의 군으로 나뉘는데 각 군은 이 군의size를 교환해야만 제자리로 돌아갈 수 있다. 따라서 문제는 n이라는 수를 k개(1=
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.
좋은 웹페이지 즐겨찾기
