Uva 11077 Find the Permutation
可以发现最优的方案就是一个循环节内互换。
所以一个有n个元素，c个循环节的置换的交换次数(最少)是n-c。
然后就可以递推了，把i插入到前i-1个元素构成的置换中，要么新成立一个循环，要么加入到之前的任意循环中去。
所以f[i][j]=f[i-1][j]+f[i-1][j-1]*(i-1)
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define ll unsigned long long
ll f[25][25];
int n,k;
inline void init(){
f[0][0]=1;
for(int i=1;i<=21;i++)
for(int j=0;j<i;j++){
f[i][j]=f[i-1][j];
//i自己独立形成一个循环
if(j) f[i][j]+=f[i-1][j-1]*(ll)(i-1);
//i插入之前循环的任意一个位置
}
}
int main(){
init();
while(scanf("%d%d",&n,&k)==2){
if(!n&&!k) break;
printf("%llu
",f[n][k]);
}
return 0;
}