题目大意
给定n个数字，规定一种 cute 排序：序列中的数字大小为严格的波浪形，即 a[0] > a[1] < a[2] > a[3] < .... 或者 a[0] < a[1] > a[2] < a[3] .....。对于N个数字来说，可以构成多个cute序列，这些序列按照字典序进行排序，求出第k个序列。
题目分析
一、求字典序的第i个排列
直接一位一位枚举答案！从前到后枚举求得每一位：枚举一位时，计算在这样的前缀下，后面的总的排列数。如果严格小于总编号，则该位偏小，换更大的数，同时更新总编号；若大于等于，则该位恰好，枚举下一位，总编号不用更新。
二、使用动态规划
由于题目要求按照字典序的第k个cute序列，因此我们需要在字典序中，n个数字构成的cute序列以第i大为开头的有多少个。这样一个计数问题，有子结构 + 无后效性（需要进一步证明）， 因此考虑使用动态规划。
一般使用动态规划来解决问题需要问题满足几个条件： （1）可以划分子问题，子问题与总问题相似 （2）无后效性 由n个数字构成的cute序列（波浪形序列）中，其连续的n-1个数字肯定也是cute序列； 无后效性，在设计状态，并用动归数组dp表示状态、推演状态的时候，需要保证当前点以后的状态只和当前点的状态有关，而与当前点是如何到达（未来的状态只和当前点的当前数值有关，和过去到当前点的路径的无关）。首先考虑 A[n] 表示n个数字构成的cute序列的总数，显然太粗糙，不知道n个数字之间的关系，无法进行状态推演； 然后考虑 A[n][i] 表示由n个数字构成的，且以n个数字中第i大为开头的cute序列的总数，这样来进行状态推演的时候，A[n][i] = sum-of(A[n-1][k])，选择哪些k，和i和k的大小关系有关，因此不能保证无后效性； 因此考虑使用 Up[n][i] 表示n个数字构成的，且以第i大为首的上升序列（a[1] > a[0])的个数；Down[n][i]表示n个数字构成的，以第i大为首的下降序列(a[1] < a[0])的个数，这样，就有递推关系：
for (int k = i; k <= m - 1; k++){ Up[m][i] += Down[m - 1][k]; } for (int k = 1; k < i; k++){ Down[m][i] += Up[m - 1][k]; }
实现 (c++)
#define _CRT_SECURE_NO_WARNINGS#include#include #include #include using namespace std;#define MAX_COL_NUM 22long long int Up[MAX_COL_NUM][MAX_COL_NUM];long long int Down[MAX_COL_NUM][MAX_COL_NUM];int main(){ int T, N; long long int C; scanf("%d", &T); //用动态规划，先求出dp数组。 //Up表示开始是上升（即A[1] > A[0]) 的波浪数组， Down表示开始是下降的波浪数组 //Up[n][i] 表示有n个数组成的序列，将第i大的数作为第一位的上升序列的个数 //Down[n][i] 表示由n个数组成的序列，将第i大的数作为第一位的下降序列个数 memset(Up, 0, sizeof(Up)); memset(Down, 0, sizeof(Down)); Up[1][1] = 1; Down[1][1] = 1; for (int m = 1; m <= MAX_COL_NUM - 1; m++){ for (int i = 1; i <= m; i++){ for (int k = i; k <= m - 1; k++){ Up[m][i] += Down[m - 1][k]; } for (int k = 1; k < i; k++){ Down[m][i] += Up[m - 1][k]; } } } while (T--){ scanf("%d %llu", &N, &C); //候选序号，存放在vector中，便于删除 vector candidates; candidates.push_back(0); for (int m = 1; m <= N; m++){ candidates.push_back(m); } int result[MAX_COL_NUM]; //存放最后求出的序列 int n = N; long long int left = C; //字典序第k大的序列 int next_dir = 2; //下一次选用的首数字和第二个数字构成上升还是下降序列，由之前序列的趋势决定 //0, 下降； 1上升； 2 both //开始设为2，表示总序列的第一个和第二个之间的关系不明确 while (n >= 1){ int k = 1; //n 表示，此次循环是在n个数中选择 //k 表示，此次选择n个数的第k大（这n个数放在 vector candidate中）去构成序列 while (k <= n){ if (next_dir == 0 && candidates[k] > result[N-n-1]){ if (left > Down[n][k]){ left -= Down[n][k]; } else{ break; } } if (next_dir == 1 && candidates[k] < result[N-n-1]){ if (left > Up[n][k]){ left -= Up[n][k]; } else{ break; } } if (next_dir == 2){ if (left > (Up[n][k] + Down[n][k])){ left -= (Up[n][k] + Down[n][k]); } else{ break; } } k++; } if (k > n) k = n; result[N - n] = candidates[k]; next_dir = ! next_dir; //波浪形数组，方向取反 //当选择出来第一个数字之后，可以根据 left (剩余的序号）以及 Down[n][k](以选择出来的数字为开头的下降序列的个数 ) 决定 //如果 剩余的序号 小于等于 以选择出来的数字为开头的下降序列总数，则说明 第一个数字和第二个数字为下降，之后的next_dir 为上升 //否则，为下降 if (n == N){ if (left <= Down[n][k]) next_dir = 1; else{ left -= Down[n][k]; next_dir = 0; } } //从候选数组中删除已经选择出来的那个数 candidates.erase(candidates.begin() + k); n --; } for (int i = 0; i < N; i++){ printf("%d ", result[i]); } printf("\n"); } return 0;}