题解 | #数列还原c++#

//...dfs退出条件，随手写了一个res==n，最后花了42分钟，找这个，res==k //两个数组一个用来保存完整输入，一个用来保存没有输入的（1...n中没有输入的数） //dfs到底之后才会进入下一个，不用担心vector遍历混乱的问题，与bfs区分 //然后这道题算入门难度中高的了，回溯，全排列，递归和dfs

#include<vector>
#include<map>
using namespace std;

class solution
{
        vector<int> vt;
        vector<int> book;
        map<int,bool> mp;    
        int k;
        int n;
        
        int count_for_k()
        {
            int count = 0;
            for(int i=0;i<n-1;i++)
                for(int j=i+1;j<n;j++)
                    if(vt[i]<vt[j]) count++;
            return count;
        }
    
        public:
         int res = 0;
    
            solution(vector<int> vt_,vector<int> book_,int k_)
        {
            vt = vt_;
            n = vt.size();
            book = book_;
            k = k_;
        }
        
            void dfs(int step)
            {
                if(step==n)
                {
                    if(count_for_k()==k) res++;
                    return;
                }
                if(vt[step]!=0)
                    dfs(step+1);
                else
                {
                    for(int num:book)
                    {
                        if(!mp[num]) 
                        {
                            mp[num] = true;
                            vt[step] = num;
                            dfs(step+1);
                            mp[num] = false;
                            vt[step] = 0;
                        }
                    }
                }
                
            }
        
};

int main(void)
{
    int n,k;

    while(cin>>n>>k)
    {
        
        int tmp;
        vector<int> vt(n);
        vector<int> book;
        map<int,bool> mp;
        
        for(int i=0;i<n;i++)
        {
            cin>>vt[i];
            mp[vt[i]]=true;
        }
        
        for(int i=1;i<=n;i++)
                if(!mp[i]) book.push_back(i);
        
        solution s(vt,book,k);
       
        s.dfs(0);
        
        cout<<s.res<<endl;
        
    }
        
    return 0;
}