牛牛摆木棒

如果只考虑第k个序列，f[i][j]表示由i根棍组成的j高度开头的种类数即可。
但是要求是波浪形，那么考虑加一维状态
dp[i][j][0/1]表示用i根木棒，首位选择第j短的长度，类型为上凸或者下凹的排列数。
(定义第二根比第一根长的为1，反之为0)。状态转换方程如下：
dp[i][j][0] = sum(dp[i-1][k][1]) 其中k=j...i-1;
dp[i][j][1] = sum(dp[i-1][k][0]) 其中k=1...j-1;
边界初始化：dp[1][1][0] = dp[1][1][1] = 1;
时间复杂度O() 空间复杂度 O(n)

const int N = 20 + 5;
ll c, dp[N][N][2];
int n, ans[N];
bool vis[N];


class Solution {
public:
    /**
     * 
     * @param n int整型 见题意
     * @param k long长整型 见题意
     * @return int整型vector
     */
    vector<int> stick(int n, long long c) {
        // write code here
        dp[1][1][0] = dp[1][1][1] = 1;
        for(int i = 2; i <= 20; i ++)
            for(int j = 1; j <= i; j ++)
            {
                for(int k = j; k <= i - 1; k ++) dp[i][j][0] += dp[i - 1][k][1];
                for(int k = 1; k < j; k ++) dp[i][j][1] += dp[i - 1][k][0];
            }
        for(int i = 1; i <= n; i ++)
        {
            int now = 0;
            ll cnt = 0;
            for(int j = 1; j <= n; j ++)
            {
                if (!vis[j])
                {
                    now ++;
                    if (i == 1)  cnt = dp[n][now][0] + dp[n][now][1];
                    else
                    {
                        if (j > ans[i - 1] && (i <= 2 || ans[i - 1] < ans[i - 2]))
                            cnt = dp[n - i + 1][now][1];
                        if (j < ans[i - 1] && (i <= 2 || ans[i - 1] > ans[i - 2]))
                            cnt = dp[n - i + 1][now][0];
                    }

                    if (cnt < c)
                    {
                        c -= cnt;
                        continue;
                    }
                    else
                    {
                        ans[i] = j;
                        vis[j] = 1;
                        break;
                    }
                }
            }

        }
        vector<int> A;
        for(int i = 1; i <= n; i ++) A.push_back(ans[i]);
        return A;
    }
};