题解 | #数列还原#

import java.io.; import java.util.;

public class Main { public static int res = 0; public static int[] nums, cands; public static boolean[] seen; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = null; while ((str = br.readLine()) != null) { if (str.equals("")) continue; String[] params = str.split(" "); int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]); params = br.readLine().split(" "); Set set = new HashSet(); for (int i = 1; i <= n; i++) set.add(i); nums = new int[n]; // 保存排列 List pos = new ArrayList(); // 记录需要填充的位置 for (int i = 0; i < n; i++) { nums[i] = Integer.parseInt(params[i]); if (nums[i] == 0) pos.add(i); else set.remove(nums[i]); }

        int count = pos.size();  // 记录需要填充的个数
        cands = new int[count]; // 记录需要填充的数字
        int index = 0;
        for (int temp: set) cands[index++] = temp;
        
        int base = 0;  // 记录已有部分包含的顺序对数量
        for (int i = 0; i < n; i++){
            if (nums[i] > 0) {
                for (int j = i + 1; j < n; j++) {
                    if (nums[i] < nums[j]) base++;
                }
            }
        }
        
        seen = new boolean[count];  // 用于遍历数组
        res = 0;
        dfs(pos, 0, count, base, k ,n);
        System.out.println(res);
    }
    br.close();
}

public static void dfs(List<Integer> pos, int index, int count, int base, int k, int n) {
    if (index == count) {
        if (base == k) res++;
    } else {
        int position = pos.get(index);  // 此时要插入的位置
        for (int i = 0; i < count; i++) {
            if (seen[i]) continue;
            // 进行深度遍历
            seen[i] = true;
            nums[position] = cands[i];
            int amount = 0;
            for (int j = 0; j < position; j++)
                if (nums[j] < cands[i]) amount++;
            for (int j = position+1; j < n; j++)
                if (cands[i] < nums[j]) amount++;
            dfs(pos, index+1, count, base+amount, k, n);
            // 还原现场
            nums[position] = 0;
            seen[i] = false;
        }
    }
}

}