题解 | #数列还原#

using System;
using System.Collections;
using System.Collections.Generic;
public class Program {
    public static void Main() {
        string line;
        while ((line = System.Console.ReadLine ()) != null) { // 注意 while 处理多个 case
            string[] tokens = line.Split(' ');
            int n = int.Parse(tokens[0]);
            int k = int.Parse(tokens[1]);
            line = Console.ReadLine();
            tokens = line.Split(' ');
            int[] a = new int[n];
            List<int> choice = new List<int>();
            for(int i = 0; i < n; i++) {
                a[i] = int.Parse(tokens[i]);
                choice.Add(i + 1);
            }
            foreach(int i in a){
                if(i != 0) choice.Remove(i);
            }
            Console.WriteLine(recursion(0,a,choice,k));
        }
    }
    //递归回溯
    public static int recursion(int index, int[] a, List<int> choice, int k) {
        int count = 0;
        if (choice.Count == 0) {
            if (k == sequence(a)) count++;
            return count;
        }
        while (a[index] != 0) {
            index++;
        }
        for (int i = 0; i < choice.Count; i++){
            a[index] = choice[i];
            choice.RemoveAt(i);
            count += recursion(index + 1, a, choice, k);
            choice.Insert(i, a[index]);
            a[index] = 0;
        }
        return count;
    }
    public static int sequence(int[] a) {
        int count = 0;
        for (int i = 0; i < a.Length; i++) {
            for (int j = i + 1; j < a.Length; j++) {
                if (a[i] < a[j]) count++;
            }
        }
        return count;
    }
}

用choice装可以选择放入的数，用a装原数组

定义一个递归，每次处理index开始的第一个0，列举所有的情况将choice中的数加入a的对应位置，然后递归调用自身。当choice.count==0时，调用sequence函数得到a中顺序对的数量，与k比较，==k则count++；return count；