| 题目名称 | 1258. K 上升段 |
|---|---|
| 输入输出 | k.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-11-08加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：37， 提交：64， 通过率：57.81% | ||||
 digital-T |
100 | 0.000 s | 0.17 MiB | Pascal |
 稠翼 |
100 | 0.001 s | 0.17 MiB | Pascal |
 Lyre |
100 | 0.001 s | 0.17 MiB | Pascal |
 ConanQZ |
100 | 0.001 s | 0.17 MiB | Pascal |
 luschegde |
100 | 0.002 s | 0.17 MiB | Pascal |
 苏轼 |
100 | 0.002 s | 0.17 MiB | Pascal |
 o_o |
100 | 0.002 s | 0.17 MiB | Pascal |
 王者自由 |
100 | 0.002 s | 0.29 MiB | C++ |
 Dijkstra |
100 | 0.002 s | 0.31 MiB | C++ |
 Launcher |
100 | 0.002 s | 0.33 MiB | C++ |
| 本题关联比赛 | |||
| 20121108 | |||
| 关于 K 上升段 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
不知道大家怎么做的，我花了一个小时想算法，后来写了个爆搜找规律。
f[i][j]=f[i-1][j]*j+f[i-1][j-1]*(i+1-j); 后来还是0分，文件名写错了。 | ||||
|
简单动归，蛋疼的是开longint会爆- -！ 囧~
dp[i,j]表示前i个有j个上升序列的个数，方程dp[i,j]:=dp[i-1,j-1]*(i-j+1)+dp[a-1,b]*b ，意思是要转移成当前状态需要两种状态转移过来，分别对应加上当前数后序列个数增加和不增加两种情况，边界值dp[i,1]:=1,i∈[1,n]. | ||||
|
如果暴力枚举的话，算出n=20的情况需要15000年
 Makazeu
2012-11-08 17:41
5楼
| ||||
|
由于前一天比赛的原因，我还是写了高精度。。。应该先验证一下要不要写的。。。
| ||||
|
从10X10的表找规律，
然后每个程序现场打表（好浪费……），再输出 | ||||
|
先用 STL 枚举出来一个表（算到 n=12 就出不来了）
1: 1然后找规律 \[ f_{i, j} = (i - j + 1) \times f_{i-1, j-1} + j \times f_{i-1, j} \] 要用 long long ，高精度暂时不必～ | ||||
|
先暴力next_permutation，然后递推。
Makazeu
2012-11-08 15:26
1楼
| ||||
怡红公子
天下第一的吃货殿下
张来风飘
Truth.Cirno【题目描述】
对于自然数 1..n 的一个排列 A[1..N] 可以划分为若干个单调递增序列。每个单调递增序列由连续元素 A[st..ed] 组成，且满足以下条件：
1<=st,ed<=n;
A[i]<A[i+1] (st<=i<=ed-1);
ed=n 或者 A[ed] > A[ed+1] ；
例如：排列 1 2 4 5 6 3 9 10 7 8 可划分为 3 个单调递增序列 1 2 4 5 6； 3 9 10 ； 7 8 ；
所以我们称这是一个 3 上升段序列 。
现在给定 n 和 k , 求出 n 的全排列中的， k 上升段序列 的个数。
【输入格式】
输入仅有 1 行，包含两个数 n, k （ 1 < n <= 20, 1 < k <= n ）。
【输出格式】
输出 n 的所有 k 上升段的个数。
【样例输入】
3 2
【样例输出】
4
【提示】
说明，符合条件的排列是１３２，３１２，２１３，２３１