首页 > > 程序设计 > C/C++ >

NOIp模拟1 Permutation

2018-06-17 22:05:07来源：未知阅读 ()

试题描述

将 1 到 N 任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。
问在所有排列中，有多少个排列恰好有K个“<”。
例如排列(3, 4, 1, 5, 2)
3 < 4 > 1 < 5 > 2
共有2个“<”

输入格式

N,K

输出格式

答案

输入示例

5 2

输出示例

注释说明

20%数据：N <= 10
50%数据：答案在0..2^63-1内
100%数据：K < N <= 100

【分析】

dp[i][j]表示在前i个数中插入j个‘<’的方案数。

由于按顺序插入，所以每次插入的数都是当前序列中最大的，首先考虑在被'<'连接的两个数之间插入，这时'<'的数目不会改变，注意在序列的最左边插入也是一样的效果，所以我们得到了dp方程的第一项dp[i-1][j]*(j+1)。

再考虑在被'>'连接的两个数间插入，这时'<'数目会增加一，当i个数中有j个'<'时，'>'的数目为i-1-j，但与上面那种情况同理，在序列的最左端插入也会多一个'<'，所以我们得到了dp方程的第二项dp[i-1][j-1]*(i-j)。

最后得到的方程为dp[i][j]=dp[i-1][j]*(j+1)+dp[i-1][j-1]*(i-j)。

初始化条件为dp[i][0]=1(1<=i<=n)，即当前序列为严格下降序列。

【代码】

50分（不加高精）：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 long long dp[105][105];
 5 int n, k;
 6 
 7 int main() {
 8     cin >> n >> k;
 9     for (int i=1;i<=n;++i) dp[i][0]=1;
10     for (int i=1;i<=n;++i)
11         for (int j=1;j<=min(k, i-1);++j)
12             dp[i][j]=dp[i-1][j]*(j+1)+dp[i-1][j-1]*(i-j);
13     cout << dp[n][k] << endl;
14 }

满分程序：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 size_t int_to_Bigint (const int& x, int* data) {
 5     size_t len=0;
 6     int nx=x;
 7     while (nx>0) {
 8         data[len++]=nx%10;
 9         nx=nx/10;
10     }
11     return len;
12 }
13 
14 struct Bigint {
15     int* data;
16     size_t len;
17 
18     Bigint& operator=(const int& x) {
19         size_t tmp = int_to_Bigint(x, data);
20         getlen(tmp);
21         check();
22         return *this;
23     }
24 
25     Bigint() : data(new int[500]), len(0) {
26         memset(data, 0, sizeof(int) * 500);
27      }
28 
29     void getlen(size_t tmp) {
30         if (tmp > len)
31             len = tmp;
32         else
33             while (len > tmp) data[--len] = 0;
34     }
35 
36     void check() {
37         while (len > 0 && data[len - 1] == 0) --len;
38     }
39 
40 
41     Bigint& operator+=(const Bigint& x) {
42         if (x.len > len) len = x.len;
43             for (size_t i = 0; i < len; ++i) {
44                 data[i] += x.data[i];
45                 if (data[i] >= 10) {
46                     data[i] -= 10;
47                     ++data[i + 1];
48                 }
49             }
50         ++len;
51         check();
52         return *this;
53     }
54 
55     Bigint& operator*=(const Bigint& x) {
56         Bigint now;
57         for (size_t i=0;i<len;++i)
58             now.data[i]=data[i], data[i]=0;
59         now.len = len;
60         for (size_t i = 0; i < len; ++i)
61             for (size_t j = 0; j < x.len; ++j) {
62                 data[i + j] += now.data[i]*x.data[j];
63             }
64         len += x.len;
65         for (size_t i = 0; i < len; ++i)
66             data[i + 1] += (data[i] / 10), data[i] %= 10;
67         if (data[len - 1] == 0)
68             len--;
69         return *this;
70     }
71 };
72 
73 void print(Bigint a) {
74     if (!a.len)
75         cout << 0;
76     for (int i = a.len - 1; i >= 0; --i)
77         cout << a.data[i];
78 }
79 
80 int n, k, ii, jj;
81 Bigint dp[105][105], t, tt, init;
82 
83 int main() {
84     init=1;
85     cin >> n >> k;
86     for (int i = 1; i <= n; ++i)
87         dp[i][0]=init;
88     for (int i = 1; i <= n; ++i)
89         for (int j = 1; j <= min(i, k); ++ j) {
90             jj = j + 1, ii = i - j;
91             t = jj, tt = ii, t *= dp[i - 1][j], tt *= dp[i - 1][j - 1];
92             dp[i][j] += t, dp[i][j] += tt;
93         }
94     print(dp[n][k]);
95     cout << endl;
96 }