5、不等式数列--百度2017春招

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 
 6 void swap(int* p1,int* p2)
 7 {
 8     int temp = *p1;
 9     *p1 = *p2;
10     *p2 = temp;
11 }
12 vector<vector<int> > res;
13 //获得1-n 全排列的个数，并存储全排列结果
14 void recall(int* arr,int len,int index,int *count)
15 {
16     vector<int> tmp;
17     if (index<=0)
18     {
19         (*count)++;//由于优先级的关系，记得加括号
20         for(int i=0;i<len;i++)
21         {
22             //cout<<arr[i]<<" ";
23             tmp.push_back(arr[i]);
24         }
25         res.push_back(tmp);
26         tmp.clear();
27         //cout<<endl;
28         return;
29     }
30     for (int i=index;i>=0;i--)
31     {
32         swap(&arr[index],&arr[i]);
33         recall(arr,len,index-1,count);
34         swap(&arr[index],&arr[i]);
35     }
36 }
37 
38 
39 int main()
40 {
41     int n;
42     int k;
43     while(cin>>n>>k)
44     {
45         int count = 0;
46         int result = 0;
47         int a[n];
48 
49         for(int i=0;i<n;i++)
50         {
51             a[i] = i+1;
52         }
53         recall(a,n,n-1,&count);
54         //cout<<count<<endl;
55         for(int i=0;i<count;i++)
56         {
57             int xiaoyu = k;
58             int dayu = n - k - 1;
59             for(int j=0;j<n-1;j++)
60             {
61                 //cout<<res[i][j]<<"  ";
62                 if(res[i][j]< res[i][j+1])
63                 {
64                     xiaoyu--;
65                 }
66                 else if(res[i][j]>res[i][j+1])
67                 {
68                     dayu--;
69                 }
70             }
71             //cout<<endl;
72             //cout<<"k"<<xiaoyu<<"add"<<dayu<<endl;
73             if(xiaoyu==0 && dayu == 0)
74             {
75                 result++;
76             }
77         }
78         cout<<result%2017<<endl;
79     }
80     return 0;
81 }